AC代码

#include<bits/stdc++.h>
using namespace std;
int first[100005],nxt[100005],to[100005],tot=0;
void Add(int x,int y){
	nxt[++tot]=first[x];
	first[x]=tot;
	to[tot]=y;
}
int n,m,a[105],vis[105],maxn=-1,ans[105];
bool pd(){
	for(int i=1;i<=n;i++){
		if(vis[i]<ans[i])  return 0;
		if(vis[i]>ans[i])  return 1;
	}
}
int main(){
	srand(time(0));
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		a[i]=i;
	}
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		Add(x,y);
		Add(y,x);
	}
	for(int i=1;i<=200000;i++){
		memset(vis,-1,sizeof(vis));
		random_shuffle(a+1,a+n+1);
		int num=0;
		for(int i=1;i<=n;i++){
			if(vis[a[i]]==-1){
				num++,vis[a[i]]=1;
				for(int e=first[a[i]];e;e=nxt[e]){
					if(vis[to[e]]==-1)  vis[to[e]]=0;
				}
			}
		}
		if(num>maxn){
			maxn=num;
			for(int i=1;i<=n;i++){
				ans[i]=vis[i];
			}
		}
		if(num==maxn){
			if(pd()){
				for(int i=1;i<=n;i++){
					ans[i]=vis[i];
				}
			}
		}
	}
	cout<<maxn<<endl;
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	}
}