2017icpc beijing-I题-Colored Nodes

#include<iostream> //找出循环节把循环节中的元素第二个n次的都加起来除以n 
#include<cstring> 
#include<algorithm>
using namespace std;
struct node{
	int next,to;
}start[200005];   //用前向星记录
int cnt;
int head[100005];  //前向星记录每个节点的下一个节点
int jl[100005];    //
int jxys[100005];  //记录下每个节点的颜色数
int ans[100005];   //记录下每个颜色在一个循环节之后的所有的总数
bool pd[100005]; //记录下哪个颜色循环节中存在
int jx[100005];  //记录下在循环节中可以存在颜色便于之后循环
bool cmp (int x,int y){  //用于sort升序
	return x>y;
}
void add(int u,int v){ //记录双向因为是无向的链接   增加
	start[cnt].to =v;  
	start[cnt].next = head[u];
	head[u] = cnt++；
	start[cnt].to = u;
	start[cnt].next = head[v];
	head[v] = cnt++;
}
int main()
{
	int n,m;
	while(~scanf("%d %d",&n,&m)){
		cnt=0;
		for(int i=1;i<=n;i++) jl[i]=i;
		memset(head,-1,sizeof(head));  //初始化为-1 
		memset(jxys,0,sizeof(jxys));   //初始的时候都初始化为0便于后边计算 
		memset(ans,0,sizeof(ans));     //ans是记录每个的最后的数 
		memset(pd,0,sizeof(pd)); 
		memset(jx,0,sizeof(jx));
		int a,b;
		for(int i=0;i<m;i++){
			scanf("%d %d",&a,&b);
			add(a,b); 
		}
		for(int i=1;i<=n;i++){
			int cnt;
			for(int j=head[i];j!=-1;j=start[j].next){
				cnt = start[j].to;
				jl[cnt] = jl[i];
			}
		}

		
		for(int i=1;i<=n;i++){
			pd[jl[i]]=1;  //判断每个节点  jl[i]是记录下在一个循环节中的n个点中的颜色然后pd记录每个颜色的是否存在
		}
		int cnt=1;
		for(int i=1;i<=n;i++){
			if(pd[i]) jx[cnt++]=i;  //jx记录记下存在的颜色
		}
		


		for(int i=1;i<=n;i++){ //在n次之后的颜色变化 
			jxys[jl[i]]++;        //记录下啊所有的颜色数
		}
		
//		for(int i=1;i<=n;i++){
//			printf("%d\n",jxys[i]);
//		}
//		system("pause");

		for(int i=1;i<=n;i++){
			int cnt1;
			for(int j=head[i];j!=-1;j=start[j].next){
				cnt1 = start[j].to;
				jxys[jl[cnt1]]--;    //把和i相连的点的颜色减去1
				jl[cnt1] = jl[i];
				jxys[jl[i]]++;     //把i的节点的颜色加上1
			}
			for(int j=1;j<cnt;j++){    //这里的时候不能每次都到n容易超时
//				printf("%d ",jxys[jx[j]]);
				ans[jx[j]]+=jxys[jx[j]];   //ans把每种颜色都加下来
			}
//			system("pause");
		}
		sort(ans+1,ans+n+1,cmp);
		
		for(int i=1;i<=n;i++){
			if(ans[i]){
				printf("%.6lf\n",(ans[i]*1.0)/(n*1.0)); 
			}
			else break;
		}
//		for(int i=1;i<cnt;i++){
//			printf("%d\n",ans[jx[i]]);
//		}
	}
}