题意
给定一个n个点m条边的无向图，一开始点i的颜色为i，在第i+kn秒开始时，与节点i相邻的节点会被染成i的颜色（k为自然数）
定义D(i,j)第j秒结束时颜色为i的节点个数，求： $F(i)=\lim_{n -> \infty }{1\over n}\sum_{j=1}^{n}D(i,j)$
题解
首先模拟一轮染色过程，求出一轮下来，每个点最终会被染成开始时哪个点的颜色。这个染色结果是一个满射。将这个映射迭代无数次，就相当于染色无数轮。由于映射是满射，迭代的过程中，每个点的颜色会形成一个循环。求出这个循环，就知道每轮结束时每个点的颜色循环情况。最后再模拟一次染色过程，就能求出每个点在每个时刻的颜色循环情况。这样就能求出每个颜色的分数解，转成小数输出即可。
代码看网上的代码，并不能AC
#include<bits/stdc++.h> using namespace std; const int maxn = 100000 + 10; struct Edge{ int next, to; }edges[2*maxn]; int head[maxn], id; void add(int u, int v) { edges[id].to = v; edges[id].next = head[u]; head[u] = id++; } int n, m; int ans[maxn]; int color[maxn]; bool vis[maxn]; int kind[maxn], color_num[maxn]; bool cmp(int x, int y) { return x > y; } int main() { while(scanf("%d%d", &n, &m) == 2) { id = 0; //memset(head, -1, sizeof(head)); for(int i = 0;i <= n;i++) { head[i] = -1; vis[i] = 0; color_num[i] = 0; ans[i] = 0; kind[i] = 0; color[i] = i; } //for(int i = 1;i <=n;i++) color[i] = i; //memset(vis, 0, sizeof(vis)); //memset(color_num, 0, sizeof(color_num)); //memset(ans,0,sizeof(ans)); //memset(kind, 0, sizeof(kind)); for(int i = 0;i < m;i++) { int a, b; scanf("%d%d", &a, &b); add(a, b); add(b, a); } for(int i = 1;i <= n;i++) for(int j = head[i];j != -1;j = edges[j].next) { int v = edges[j].to; color[v] = color[i]; } for(int i = 1;i <= n;i++) vis[color[i]] = true; //哪些颜色出现过 int cnt = 1; for(int i = 1;i <= n;i++) if(vis[i]) kind[cnt++] = i; //第cnt种颜色为i for(int i = 1;i <= n;i++) color_num[color[i]]++; //for(int i = 1;i <= n;i++) printf("%d\n", kind[i]); for(int i = 1;i <= n;i++) { for(int j = head[i];j != -1;j = edges[j].next) { int v = edges[j].to; color_num[color[v]]--; //把与i相连的颜色减去1 color[v] = color[i]; color_num[color[i]]++; } for(int j = 1;j < cnt;j++) //对于每种颜色 ans[kind[j]] += color_num[kind[j]]; } //sort(ans+1, ans+n+1, cmp); for(int i = 1;i <= n;i++) { if(ans[i]) printf("%.6f\n", ans[i]*1.0/n); //else break; } } return 0; }
参考链接：
1. https://blog.csdn.net/qq_37699336/article/details/83244519