hihocoder1635_Colored_Nodes

题目传送门
题意:略……

暴力染色一轮,然后可以得到每个点的颜色是从哪个点转移过来的,类似于等到了一个点的颜色转移矩阵.
如果点$i$的前驱是$fa_{i}$,则连边$fa_{i}->i$,然后可以得到一些基环外向树,可以知道每棵树只有一个环,树上的点的颜色会被环上的点等频率的染色到.然后把每棵树重新定义一种颜色,模拟一轮染色,就可以得到这棵树在一轮染色中占有了的点的个数.一轮染色染$n$次,总共$n^{2}$个点.那么每棵树的答案即是$\frac{sum}{num * n}$,$sum$为占有的点的个数,$num$为环上点的个数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//created by missever
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
vector<int> g[maxn];
vector<double> ans;
int c[maxn],d[maxn],pre[maxn],cnum[maxn],tot,col;
LL csum[maxn];
int dfs(int u) {
if(d[u] == -1) {
d[u] = col++;
cnum[d[u]]++;
return u;
} else if(d[u]) return 0;
d[u] = -1;
int dx = dfs(c[u]);
d[u] = d[c[u]];
if(dx == 0 || dx == u) return 0;
else {
cnum[d[u]]++;
return dx;
}
}
int main() {
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int n,m,i,u,v;
while(~scanf("%d%d",&n,&m)) {
for(i = 1; i <= n; i++) {
g[i].clear();
c[i] = i;
}
memset(pre,0,sizeof(pre));
memset(d,0,sizeof(d));
memset(csum,0,sizeof(csum));
memset(cnum,0,sizeof(cnum));
ans.clear();
for(i = 0; i < m; i++) {
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
for(i = 1; i <= n; i++) {
for(auto x:g[i]) c[x] = c[i];
}
for(i = col = 1; i <= n; i++) {
if(!d[i]) dfs(i);
}
for(i = 1; i <= n; i++) {
for(auto x:g[i]) {
if(d[x] != d[i]) {
csum[d[x]] += i - pre[x];
d[x] = d[i];
pre[x] = i;
}
}
}
for(i = 1; i <= n; i++) csum[d[i]] += n - pre[i];
for(i = 1; i < col; i++) {
double fs = 1.0 * csum[i] / n / cnum[i];
for(v = 0; v < cnum[i]; v++) ans.push_back(fs);
}
sort(ans.rbegin(),ans.rend());
for(auto x:ans) printf("%.6f\n",x);
}
return 0;
}