题目大意
K 国是一个热衷三角形的国度，连人的交往也只喜欢三角原则。他们认为三角关系：即 AB 相互认识，BC 相互认识，CA 相互认识，是简洁高效的。为了巩固三角关系，K 国禁止四边关系，五边关系等等的存在。所谓 N 边关系，是指 N 个人 A1 A2 ... An 之间仅存在 N 对认识关系：(A1 A2) (A2 A3) ... (An A1)，而没有其它认识关系，比如四边关系指 A B C D 四个人 AB，BC，CD，DA 相互认识，而 AC，BD 不认识。全民比赛时，为了防止做弊，规定任意一对相互认识的人不得在一队，国王相知道，最少可以分多少支队。
Input
第一行两个整数 N，M。1<=N<=10000，1<=M<=1000000。表示有 N 个人，M 对认识关系.。接下来 M 行每行输入一对朋友
Output
输出一个整数，最少可以分多少队
做法分析
根据提题意，不难看出，所有的人构成的关系图是一个弦图（长度超过 3 的环中必有一条弦），求出它的完美性消除序列，根据完美消除序列逆序贪心的染色，最终所用的色数就是本题的答案
完美消除序列的求法：
使用陈丹琦讲述的 MCS 法，可以在 o(n+m) 的时间复杂度中求出一个图的完美消除序列，并在 o(n+m) 的时间复杂度下判断这个完美消除序列是否合法，不过，我不知道怎么在 o(n+m) 的时间复杂度下求出这个完美消除序列，或许是利用桶优化吧，我写了个堆优化的，时间复杂度也能接受
求完美消除序列的 MCS 法是倒着解的，也就是先求序列的第 n 个再求序列的第 n-1 个
每次选取图中具有最大标号的点作为完美消除序列中对应位置的点，并用这个点更新所有和他邻接的不再序列中的点的标号值
对于一个弦图的染色，用完美消除序列可以很好的解决，按照完美消除序列中的点倒着给图中的点贪心的然尽可能小的颜色
最终，一定能够用最小的颜色数量给图中的所有点染色
本题可以先求出来这个弦图的完美消除序列，由于一定是一个弦图，所以序列一定合法，直接根据消除序列染色就行
更多的和弦图区间图相关的知识，请看陈丹琦的PPT：弦图与区间图
参考代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue> using namespace std; const int N=; vector <int> arc[N];
int n, m, R[N], SA[N], label[N]; priority_queue <pair<int, int> > heap;
void Construct() {
fill(R+, R++n, -);
fill(label+, label++n, );
for(int i=; i<=n; i++) heap.push(make_pair(, i));
for(int cnt=n; cnt>=; ) {
int id=heap.top().second;
heap.pop();
if(R[id]!=-) continue;
SA[cnt]=id, R[id]=cnt--;
for(int i=, len=(int)arc[id].size(); i<len; i++) {
int u=arc[id][i];
if(R[u]!=-) continue;
label[u]++;
heap.push(make_pair(label[u], u));
}
}
} void Color(int u) {
for(int i=, len=(int)arc[u].size(); i<len; i++) {
int v=arc[u][i];
if(label[v]==-) continue;
R[label[v]]=u;
}
for(int i=; label[u]==-; i++) if(R[i]!=u) label[u]=i;
} int Color_Graph() {
fill(label+, label++n, -);
fill(R+, R++n, -);
for(int i=n; i>; i--) Color(SA[i]);
int ans=;
for(int i=; i<=n; i++) ans=max(ans, label[i]);
return ans;
} int main() {
scanf("%d%d", &n, &m);
for(int i=; i<=n; i++) arc[i].clear();
for(int i=, a, b; i<m; i++) {
scanf("%d%d", &a, &b);
arc[a].push_back(b);
arc[b].push_back(a);
}
Construct();
printf("%d\n", Color_Graph());
return ;
}
BZOJ 1006