bzoj1006 神奇的国度

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

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

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

MCS算法（每次选一个与最多已标号点相邻的点进行标号，标号顺序的逆序即为完美消除序列）求弦图的完美消除序列，

并逆序贪心染色，每次染与相邻已染色结点不同的颜色中最小编号的颜色，染色所用颜色数即为答案

时间复杂度O(n+m)

#include<cstdio>

int n,m,a,b;

int es[],ep=;

int enx[];

int ss[],ls[],rs[];

int id[],f[],col[],cols[];

int h[];

int mx=,mxc=;

inline void addedge(int a,int b){

    es[ep]=b;

    enx[ep]=enx[a];

    enx[a]=ep++;

    es[ep]=a;

    enx[ep]=enx[b];

    enx[b]=ep++;

}

inline void del(int w){

    w+=;

    rs[ls[w]]=rs[w];

    ls[rs[w]]=ls[w];

}

inline void add(int w,int x){

    w+=;

    rs[w]=rs[x];

    ls[w]=x;

    ls[rs[x]]=w;

    rs[x]=w;

}

inline int read(){

    int x=;

    char c=getchar();

    while(c>''||c<'')c=getchar();

    while(c>=''&&c<='')x=x*+c-'',c=getchar();

    return x;

}

int main(){

    n=read(),m=read();

    for(int i=;i<=n;i++)ls[i]=rs[i]=i;

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

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

        a=read(),b=read();

        addedge(a,b);

    }

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

        while(rs[mx+]!=mx+)++mx;

        while(mx&&rs[mx]==mx)--mx;

        int c=rs[mx]-;

        f[id[c]=i]=c;

        del(c);

        int e=c;

        while(e=enx[e]){

            int u=es[e];

            ++h[u];

            if(!id[u])del(u),add(u,h[u]);

        }

    }

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

        int c=f[i];

        int e=c;

        while(e=enx[e])cols[col[es[e]]]=i;

        int cn=;

        while(cols[cn]==i)++cn;

        col[c]=cn;

        if(cn>mxc)mxc=cn;

    }

    printf("%d",mxc);

    return ;

}