【图论】最大势算法

模板题Fishing Net

给定一个无向图，判断是否是弦图。

\(1 \leq n \leq 1000\)。

算法概述

最大势算法（MCS），是一个用于求出无向图完美消除序列的算法。算法流程为：

• 钦定一个集合 \(S\) 。

• 每次找到任意一个与 \(S\) 中的点连边最多的点，加入 \(S\) ，放在消除序列末尾。

这样就可以 \(\Theta(n + m)\) 求出这个序列，具体实现以连边数为下标开一个桶即可。

这个如何用于弦图判断呢？

有一些概念：

• 导出子图：一些点集，边被选入当且仅当两个端点都被选入。

• 单纯点：设一个点集 \(X\) 为一个点以及与它相邻的点， \(X\) 的导出子图是完全图，那么这个点就是单纯点。

有定理：

图是弦图的充要条件是， \(\forall i \in [1,n]\) ，\(a_i\) 是 \(a_{[i,n]}\) 导出子图的单纯点。

不会证。

这样，判断这个序列满足这个性质就好了。

从左到右检查每一位，设集合 \(X\) 是 \(a_{[i,n]}\) 中与 \(a_i\) 相邻的点，那么看 \(X\) 是否是完全图即可。

不太好判，又发现设 \(a_j\) 是 \(a_i\) 后第一个与 \(a_i\) 连边的点，那么 \(a_j\) 也会被检查一遍，这个过程是迭代的，只需要检查 \(a_j\) 与后面连接 \(a_i\) 的点是否有连边即可。

复杂度 \(\Theta(n + m)\) 。

#include<bits/stdc++.h>
using namespace std;
const int N = 2005;
vector <int> G[N];
int n,m,seq[N];
inline void MCS()
{
	static int vis[N],lab[N];
	static vector <int> pot[N];
	fill(lab,lab + n + 1,0);
	fill(vis,vis + n + 1,0); 
	for(int i = 0;i <= n;i++) pot[i].clear();
	for(int i = 1;i <= n;i++) pot[0].push_back(i);
	for(int i = n,maxn = 0;i >= 1;i--)
	{
		int flag = 0,cur;
		while(flag == 0)
		{
			while(pot[maxn].size() && vis[pot[maxn].back()]) pot[maxn].pop_back();
			if(!pot[maxn].size()) maxn--;
			else cur = pot[maxn].back(),flag = 1;
		}
		seq[i] = cur; vis[cur] = 1;
		for(auto to : G[cur])
		{
			if(vis[to]) continue;
			lab[to]++;
			pot[lab[to]].push_back(to);
			maxn = max(maxn,lab[to]);
		}
	}
}
inline bool judge()
{
	static int pos[N],vis[N];
	fill(vis,vis + n + 1,0);
	for(int i = 1;i <= n;i++) pos[seq[i]] = i;
	for(int i = 1;i <= n;i++)
	{
		int mini = n + 1;
		for(auto to : G[i]) 
			if(pos[to] > pos[i]) 
				if(mini == n + 1 || pos[to] < pos[mini])
					mini = to;
		if(mini == n + 1) continue;
		for(auto to : G[mini]) vis[to] = 1;
		for(auto to : G[i])
			if(pos[to] > pos[i] && to != mini)
				if(vis[to] == 0)
					return false;
		for(auto to : G[mini]) vis[to] = 0;
	}
	return true;
}
int main()
{
	cin>>n>>m;
	while(n > 0 && m > 0)
	{
		for(int i = 1;i <= n;i++) G[i].clear();	
		for(int i = 1,x,y;i <= m;i++)
		{
			cin>>x>>y;
			G[x].push_back(y);
			G[y].push_back(x);
		}
		MCS();
		puts(judge() ? "Perfect" : "Imperfect");
		cin>>n>>m;
	}
	return 0;
}

那么这个序列的简单应用？

[HNOI2008] 神奇的国度

求弦图的色数。

弦图的性质：团数等于色数。

如果只求数量直接对每个 \(i\) 判断 \(|X_i + 1|\) 即可，如果染色就在序列上从后往前贪心染。

[TJOI2007] 小朋友

求弦图最大独立集。

从前往后跑，我们发现选了这个点，后面相邻的就不能选，贪心即可。

考虑每个团一定只有一个点被选入，所以我们尽量不影响其他的团选点，发现对于第一个所属的一个团而言，这个团里一定有第一个点的所有相邻点。所以选完第一个点后不会影响到其他的团。