最大势算法 求 最小染色数

 

/**************************************************************
    Problem: 1006
    User: lxy8584099
    Language: C++
    Result: Accepted
    Time:1236 ms
    Memory:28828 kb
****************************************************************/
 
/*
    一个无向图称为弦图 当图中任意长度大于3的环都至少有一个弦
    最大势算法 求最小染色数 仅在弦图时成立
    每个点建立一个 point 表示标号 初始化都是 1  
    每次选择标号最大的点删掉 对其相连的点 ponit+1 
    直到剩下一个点
    其过程中出现的最大point就是最小染色数 
*/
#include<queue>
#include<cstdio>
#include<utility> 
using namespace std;
const int N=1e4+50,M=1e6+50; 
struct pp {int v,nxt;} e[M<<1]; 
bool vis[N];
int head[N],n,m,tot,point[N],ans;
priority_queue < pair < int,int > > q;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) 
    {
        point[i]=1;q.push(make_pair(1,i));
    }
    for(int i=1,u,v;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        e[++tot].nxt=head[u];head[u]=tot;e[tot].v=v;
        e[++tot].nxt=head[v];head[v]=tot;e[tot].v=u;
    }
    int num=0;
    while(num<n)
    {
        int u=q.top().second;q.pop();
        if(vis[u]) continue;
        vis[u]=1;num++;
        for(int j=head[u];j;j=e[j].nxt)
        {
            int v=e[j].v;if(vis[v])continue;
            point[v]++;q.push(make_pair(point[v],v));
            if(point[v]>ans) ans=point[v];
        }
    }
    printf("%d\n",ans);
    return 0;
}