BZOJ 1006: [HNOI2008]神奇的国度(弦图)

传送门

解题思路

　　弦图就是图中任意一个大小$>=4$的环至少存在一条两个节点不相邻的边，这样的图称为弦图，弦图有许多优美的性质。一个无向图是弦图当且仅当它有一个完美消除序列，完美消除序列就是一个点的排列满足$v_i$与$v_{i+1}..v_n$之间所有的边连上后的图是一个团。用最大势算法可以在$O(n+m)$内求出一个完美消除序列。做法就是设$lable(i)$表示与$i$这个点相邻的以标号节点数，每次找到未标号节点中$lable(i)$最大的一个点，而题目中的最小色数问题，在弦图中等于最小团数，为$max lable(i)+1$。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<vector>

using namespace std;

const int N=10005;

const int M=1000005;

inline int rd(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();

	while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	return f?x:-x;

}

int n,m,head[N],cnt,to[M<<1],nxt[M<<1],lable[N],best;

bool vis[N];

vector<int> v[N];

inline void add(int bg,int ed){

	to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;

}

int main(){

	n=rd(),m=rd(); int x,y,now;

	for(int i=1;i<=m;i++) {

		x=rd(),y=rd();

		add(x,y),add(y,x);

	}

	for(int i=1;i<=n;i++) v[0].push_back(i);

	for(int i=n;i;i--){

		while(1){

			for(int j=v[best].size()-1;~j;j--){

				if(!vis[v[best][j]]) {now=v[best][j];goto succ;}

				v[best].pop_back();

			}

			--best;

		}

		succ:; vis[now]=1;

		for(int j=head[now];j;j=nxt[j]){

			int u=to[j];if(vis[u]) continue;

			v[++lable[u]].push_back(u);

			best=max(best,lable[u]);

		}

	}

	int ans=0;

	for(int i=1;i<=n;i++) ans=max(ans,lable[i]);

	ans++; printf("%d\n",ans);

	return 0;

}