好像是一道非常神仙的题……
本题中具体的概念可以参见CDQ大神的论文：弦图与区间图
我们直接来说吧。 从这道题中的描述可以看出，由所有人向其认识的人连一条边，构成的是一张标准的弦图。而题目要求我们求出这张弦图的最小染色数。
有一个非常重要的定理：对于一张弦图，团数 = 色数（这个证明很难懂不过可以自己领会）
所以我们可以直接求最大团数。先用最大势算法求出弦图的完美消除序列，之后从后往前，将每个点所能连通的点用最小的色去染色（就是编号最小的），这样就能直接求出来最少染色数了。
代码看着非常的简单……
#include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(‘\n‘) using namespace std; typedef long long ll; const int M = 1000005; const int N = 10005; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘) { if(ch == ‘-‘) op = -1; ch = getchar(); } while(ch >= ‘0‘ && ch <= ‘9‘) { ans *= 10; ans += ch - ‘0‘; ch = getchar(); } return ans * op; } struct node { int next,to; }e[M<<1]; int n,m,len,ans,label[N],col[N],ecnt,head[N],x,y,q[N],check[N]; bool vis[N]; void add(int x,int y) { e[++ecnt].to = y; e[ecnt].next = head[x]; head[x] = ecnt; } void MCS()//这里的最大势算法没有优化……不过直接n^2跑一遍也可以 { per(i,n,1) { int now = 0; rep(j,1,n) if(label[j] >= label[now] && !vis[j]) now = j; vis[now] = 1,q[i] = now;//记录一下完美消除序列 for(int j = head[now];j;j = e[j].next) label[e[j].to]++; } } void color() { per(i,n,1) { int now = q[i],d = 1; for(int j = head[now];j;j = e[j].next) check[col[e[j].to]] = i;//从当前点能走到的点，它们上过的颜色都被记录过，我们把它们的check值记录为当前点的编号 while(d) { if(check[d] != i) break;//对于染过的每一种颜色，如果其出现过，且与当前点相连，那么必然有其check值 = i，否则我们就要新使用一种颜色。 d++; } col[now] = d; ans = max(ans,d);//新使用一种颜色并更新答案 } } int main() { n = read(),m = read(); rep(i,1,m) x = read(),y = read(),add(x,y),add(y,x); MCS(); color(); printf("%d\n",ans); return 0; }
原文：https://www.cnblogs.com/captain1/p/9534526.html