BZOJ 1006 神奇的国度

2024-03-05 20:54:37

Description

K国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.所谓N边关系,是指N个人 A1A2...An之间仅存在N对认识关系:(A1A2)(A2A3)...(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人 AB,BC,CD,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

鬼畜的论文题，参见cdq的论文《区间图与弦图》。

先利用mcs最大势算法求完美消除序列(cdq说复杂度是线性的，可是我始终还是得带个log)，再根据完美消除序列进行染色即可。

代码如下：

 #include<algorithm>

 #include<queue>

 #include<cstdio>

 #include<cstdlib>

 #include<set>

 using namespace std;

 #define maxn 10010

 #define maxc 510

 #define maxm 1000010

 int tot,n,m,cnt,color[maxn][maxc],label[maxn],all;

 int side[maxn],next[maxm*],toit[maxm*],per[maxn];

 bool in[maxn];

 struct node

 {

     int key,ord;

     friend bool operator < (node a,node b) {return a.key > b.key; }

 };

 multiset <node> S;

 inline void add(int a,int b)

 {

     next[++cnt] = side[a]; side[a] = cnt; toit[cnt] = b;

 }

 inline void ins(int a,int b){add(a,b); add(b,a);}

 inline void mcs()

 {

     int i,u;

     for (i = ;i <= n;++i) S.insert((node){,i});

     while (all < n)

     {

         u = (*S.begin()).ord; S.erase(S.begin()); if (in[u]) continue;

         in[u] = true; per[++all] = u;

         for (i = side[u];i;i = next[i])

             if (!in[toit[i]])

             {

                 label[toit[i]]++;

                 S.insert((node){label[toit[i]],toit[i]});

             }

     }

 }

 inline void paint()

 {

     int p,i,j,t;

     for (p = ;p <= n;++p)

     {

         i = per[p];

         for (j = ;j <= tot;++j)

             if (!color[i][j]) {t = j; break; }

         if (j == tot + ) t = ++tot;

         for (j = side[i];j;j = next[j])

             color[toit[j]][t] = true;

     }

 }

 int main()

 {

     freopen("1006.in","r",stdin);

     freopen("1006.out","w",stdout);

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

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

     { int a,b; scanf("%d %d",&a,&b); ins(a,b); }

     mcs();

     paint();

     printf("%d",tot);

     fclose(stdin); fclose(stdout);

     return ;

 }

码农公寓