[BZOJ1006] [HNOI2008] 神奇的国度 (弦图)

2024-02-17 13:35:49

Description

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

Input

　　第一行两个整数N，M。1<=N<=10000,1<=M<=1000000.表示有N个人，M对认识关系. 接下来M行每行输入一对朋
友

Output

　　输出一个整数，最少可以分多少队

Sample Input

4 5
1 2
1 4
2 4
2 3
3 4

Sample Output

HINT

　　一种方案(1,3)(2)(4)

Source

Solution

　　cdq《弦图与区间图》论文题

　　题意保证图为弦图，然后本题又是求最小染色，于是用$MCS$算法求一个完美消除序列，倒着贪心即可，论文里有说明

　　原论文里使用了桶排序使得其为$O(n+m)$，蒟蒻智商余额不足表示看不懂，于是用的优先队列，大概是$O((n+m)log(n+m))$

　　（咦好多人都是$O(n^2+m)$的？啊不怕不怕啦！）

 #include <bits/stdc++.h>

 using namespace std;

 struct edge

 {

     int v, nxt;

 }e[];

 int fst[], label[], s[], vis[];

 priority_queue<pair<int, int> > PQ;

 void addedge(int i, int u, int v)

 {

     e[i] = (edge){v, fst[u]}, fst[u] = i;

 }

 int main()

 {

     int n, m, u, v, ans = ;

     scanf("%d%d", &n, &m);

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

     {

         scanf("%d%d", &u, &v);

         addedge(i << , u, v);

         addedge(i <<  | , v, u);

     }

     for(int i = ; i <= n; ++i)

         PQ.push(make_pair(, i));

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

     {

         u = PQ.top().second, PQ.pop();

         while(vis[u])

             u = PQ.top().second, PQ.pop();

         s[i] = u, vis[u] = -;

         for(int j = fst[u]; j; j = e[j].nxt)

         {

             v = e[j].v;

             if(vis[v]) continue;

             PQ.push(make_pair(++label[v], v));

         }

     }

     memset(label, , sizeof(label));

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

     {

         for(int j = fst[s[i]]; j; j = e[j].nxt)

             vis[label[e[j].v]] = i;

         for(int j = ; ; ++j)

             if(vis[j] != i)

             {

                 label[s[i]] = j, ans = max(ans, j);

                 break;

             }

     }

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

     return ;

 }

码农公寓