P3196 [HNOI2008]神奇的国度（弦图的最小染色问题）

整理的算法模板合集： ACM模板

---

题目传送门

K国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在. 所谓N边关系,是指N个人 A1A2…An之间仅存在N对认识关系:(A1A2)(A2A3)…(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人 AB,BC,CD,DA相互认识,而AC,BD不认识.全民比赛时,为了防止做弊，规定任意一对相互认识的人不得在一队，国王相知道，最少可以分多少支队。

最多只有三角关系，很明显就是一个弦图（弦图就是任意大于三的环都至少有一个弦这样就不会构成四边、五边关系）将弦图分成多组的问题可以看做给弦图上的点染色且两个有直接边相连的点不能同色，这样就转化成了弦图的最小染色问题。直接跑优先队列优化的$O(nlogn+m)$的mcs算法即可。

int n,m,cnt=-1; const int MAX=2000015; int head[MAX]; bool vis[MAX],used[MAX]; int seq[MAX],label[MAX],color[MAX]; struct edge{ int nxt; int to; }e[MAX]; void add(int u,int v){ e[++cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } typedef pair<int,int>p; priority_queue<p>q; void mcs(){ for(rg int i=1;i<=n;++i) q.push(p(0,i)); for(rg int i=n;i>=1;--i){ while(vis[q.top().second]) q.pop(); int u=q.top().second; q.pop(); seq[i]=u; vis[u]=1; for(rg int i=head[u];~i;i=e[i].nxt){ if(!vis[e[i].to]) q.push(p(++label[e[i].to],e[i].to)); } } } int solve(){ int res=0; for(rg int i=n;i>=1;--i){ memset(used,0,sizeof(used)); for(rg int j=head[seq[i]];~j;j=e[j].nxt){ used[color[e[j].to]]=1; } for(color[seq[i]]=1;used[color[seq[i]]];++color[seq[i]]); res=max(res,color[seq[i]]); } return res; } int main(){ memset(head,-1,sizeof(head)); n=read(),m=read(); for(rg int i=1;i<=m;++i){ int u=read(),v=read(); add(u,v); add(v,u); } mcs(); printf("%d\n",solve()); return 0; }