题意：给出n个点m条边 然后每个时间点，与这个位置相连的所有点就会变成这个点的颜色 比如时间1的时候就是以这个位置相连的点2 变成1的颜色同理如下，通过2个循环之后除了第一次循环的时候看不出来循环节 在第二次循环的时候就已经有了循环节 然后把一个循环内的d[i][1] d[i][2] … d[i][无穷] 其实找到一个循环节之后就把这个循环节中的所有节点之和相加/n就可以得到一个值直接暴力出来循环节就行
代码语言：javascript复制#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("%dn",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("%.6lfn",(ans[i]*1.0)/(n*1.0));
}
else break;
}
// for(int i=1;i<cnt;i ){
// printf("%dn",ans[jx[i]]);
// }
}
} 
