题意

给一张弦图，求它的最小染色

最小染色：将点用最少的颜色染色，使得相邻点颜色不同

弦：连接环中不相邻的两个点的边

弦图：一个无向图称为弦图当图中任意长度大于3的环都至少有一个弦

具体参照

---

思路

最大势算法

待补充

求出原图的完美消除序列，从序列的最后一个开始每次选择目前可以选的最小颜色

在本题中做法即为：初始化每个点的\(label\)值为0，每次选出一个未被选过的\(label\)值最大的点，固定它的\(label\)值，然后将与它直接连边的未被选过点的\(label\)值\(+1\)，这个过程用链表实现即可

Code:

#include
    
     #define N 10005#define M 1000005 #define Max(x,y) ((x)>(y)? (x) : (y))using namespace std;int n,m;int label[N],nxt[N<<1],las[N<<1],best=0;bool vis[N];struct Edge{    int next,to;}edge[M<<1];int head[N],cnt=1;void add_edge(int from,int to){    edge[++cnt].next=head[from];    edge[cnt].to=to;    head[from]=cnt;}template 
     
      void read(T &x){    char c;int sign=1;    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;    while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;}void add(int i){    nxt[i]=nxt[N+label[i]];    las[i]=N+label[i];    nxt[las[i]]=i;    las[nxt[i]]=i;}void del(int i){    nxt[las[i]]=nxt[i];    las[nxt[i]]=las[i];}int main(){    read(n);read(m);    for(int i=1;i<=n;++i) add(i);//全部加入0号链表     for(int i=1;i<=m;++i)    {        int x,y;        read(x);read(y);        add_edge(x,y);        add_edge(y,x);    }    for(int i=1;i<=n;++i)    {        while(!nxt[best+N]) best--;        int now=nxt[best+N];        del(now);        vis[now]=1;        for(int j=head[now];j;j=edge[j].next)        {            int v=edge[j].to;            if(!vis[v])            {                del(v);                label[v]++;                best=Max(best,label[v]);                add(v);            }        }    }    int maxx=-1;    for(int i=1;i<=n;++i) maxx=Max(maxx,label[i]);    cout<
      
       <