BZOJ 1006 神奇的国度

题意

保证大于3人的朋友关系一定会出现弦边（即连接环上不相邻的两个点）。在分组时要求朋友关系的两人不能分在同一组，求最少分几组。

数据范围

$$人数n\leq10000\ \ \ ;\ \ \ 朋友对数m\leq1000000$$

题解

环上有弦被称为弦图，那这道题就是在弦图上做最小染色（即相邻的点不能染同一种颜色），需要用到完美消除序列的最大势算法(MCS)。
最大势算法是排序时每次找势能最大的点，并将它所连的点势能都加1，再继续找势能最大的点。具体建议去看陈丹琦的 《弦图与区间图》。
从n到1的顺序个点标号，然后倒着给点染上尽可能小的颜色，即要求不与它所连的点的颜色相同，且数最小。
最后染多少种颜色就是最少分多少组。

代码

#include<cstdio>
struct E
{
	int y,next;
}e[2000010];
int g[10010],tmp,d[10010],q[10010],hash[10010],col[10010];
bool v[10010];
void build(int u,int v)
{
	e[++tmp].y=v;e[tmp].next=g[u];g[u]=tmp;
	e[++tmp].y=u;e[tmp].next=g[v];g[v]=tmp;
}
int main()
{
	int n,m,a,b,t,ans=0;
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		build(a,b);
	}
	for (int i=n;i;i--)
	{
		int t=0;
		for (int j=1;j<=n;j++) if (!v[j]&&d[j]>=d[t]) t=j;
		v[t]=true;q[i]=t;
		for (int j=g[t];j;j=e[j].next) d[e[j].y]++;
	}
	for (int i=n;i;i--)
	{
		int t=q[i],j;
		for (j=g[t];j;j=e[j].next) hash[col[e[j].y]]=i;
		for (j=1;hash[j]==i;j++);
		col[t]=j;
		if (j>ans) ans=j;
	}
	printf("%d",ans);
	return 0;
}