bzoj 1006 MCS算法

　　根据陈丹琪的论文弦图与区间图，求出弦图的完美消除序列之后，反向给每个点染可以染的最小的颜色，这样可以使用最少的颜色染色，染色的方案即为队伍数。

　　那么我们需要求该图的完美消除序列，使用MCS算法，从后向前求完美消除序列，我们设size[i]为i这个点的标号，表示该点与多少个以标记的点相连，选取标号最大且i最大的点（即n）为序列的第n个，然后更新与i相连的点的标号，重复n次，即可得到弦图的完美消除序列，使用动态链表维护可以使时间复杂度达到O（m+n），暴力循环也有n^2，这道题暴力即可过。

/**************************************************************

    Problem: 1006

    User: BLADEVIL

    Language: C++

    Result: Accepted

    Time:1720 ms

    Memory:20492 kb

****************************************************************/

 

//By BLADEVIL

#include <cstdio>

#include <cstring>

#include <algorithm>

#define maxn 10010

#define maxm 1000010

 

using namespace std;

 

int n,m,l,ans;

int peo[maxn],size[maxn],flag[maxn],color[maxn];

int last[maxm],other[maxm<<],pre[maxm<<];

 

void connect(int x,int y){

    pre[++l]=last[x];

    last[x]=l;

    other[l]=y;

}

 

int main(){

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

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

        int x,y;

        scanf("%d%d",&x,&y);

        connect(x,y); connect(y,x);

    }

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

        int cur=;

        for (int j=;j<=n;j++) cur=!flag[j]&&size[j]>=size[cur]?j:cur;

        flag[cur]=; peo[i]=cur;

        for (int p=last[cur];p;p=pre[p]) size[other[p]]++;

    }

//for (int i=1;i<=n;i++) printf("%d ",peo[i]); printf("\n");

    memset(flag,,sizeof flag);

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

        for (int p=last[peo[i]];p;p=pre[p]) flag[color[other[p]]]=i;

        for (color[peo[i]]=;flag[color[peo[i]]]==i;color[peo[i]]++);

        ans=max(ans,color[peo[i]]);

    }

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

    return ;

}