K国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.所谓N边关系,是指N个人 A1A2...An之间仅存在N对认识关系:(A1A2)(A2A3)...(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人 AB,BC,CD,DA相互认识,而AC,BD不认识.全民比赛时,为了防止做弊，规定任意一对相互认识的人不得在一队，国王相知道，最少可以分多少支队。

第一行两个整数N，M。1<=N<=10000,1<=M<=1000000.表示有N个人，M对认识关系. 接下来M行每行输入一对朋友

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

一种方案(1,3)(2)(4)

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;#define MAXN 10010#define MAXE 2100000inline int nextInt(){        int x=0;        char ch;        while (ch=getchar(),ch<‘0‘||ch>‘9‘);        do                x=x*10+ch-‘0‘;        while (ch=getchar(),ch<=‘9‘&&ch>=‘0‘);        return x;}struct Edge{        int np;        Edge *next;}E[MAXE],*V[MAXN];int tope=-1;inline void addedge(int x,int y){        E[++tope].np=y;        E[tope].next=V[x];        V[x]=&E[tope];}int n,m;bool vis[MAXN];int cnt[MAXN];int seq[MAXN];int pos[MAXN];bool operator <(pair<int,int> p1,pair<int,int> p2){        return p1.second>p2.second;}struct cmp_c{        bool operator ()(pair<int,int> p1,pair<int,int> p2)        {                return p1.second<p2.second;        }};priority_queue<pair<int,int>,vector<pair<int,int> >,cmp_c > Q;bool fl[10000];int col[MAXN];int main(){        freopen("input.txt","r",stdin);        //freopen("output.txt","w",stdout);        int i,j,k;        int x,y,z;        scanf("%d%d",&n,&m);        for (i=0;i<m;i++)        {                x=nextInt();                y=nextInt();                addedge(x,y);                addedge(y,x);        }        int now;        int rk=n+1;        Edge *ne;        Q.push(make_pair(1,cnt[1]));        while (!Q.empty())        {                now=Q.top().first;                Q.pop();                if (vis[now])continue;                vis[now]=true;                seq[--rk]=now;                pos[now]=rk;                for (ne=V[now];ne;ne=ne->next)                {                        if (vis[ne->np])continue;                        cnt[ne->np]++;                        Q.push(make_pair(ne->np,cnt[ne->np]));                }        }        Edge *ne2;        int mx=0;        int ans=0;        for (i=n;i>=1;i--)        {                now=seq[i];                memset(fl,0,sizeof(fl[0])*(mx+1));                for (ne=V[now];ne;ne=ne->next)                {                        if (pos[ne->np]<i)continue;                        fl[col[ne->np]]=true;                        mx=max(mx,col[ne->np]);                }                for (j=1;j<=mx+1;j++)                {                        if (!fl[j])                        {                                col[now]=j;                                ans=max(ans,j);                                break;                        }                }        }        printf("%d\n",ans);}