题意分析
“不会发生污水形成环流的情况”，即无环，则整张图为一张有向无环图。
那么很容易想到拓扑排序，拓扑排序后统计贡献即可。
这道题目的难度可能就在于分数运算，但是也不难，写个结构体用 __int128 实现即可。
AC 代码
时间复杂度：$\mathcal O(n\log V)$。其中 $\mathcal O(\log V)$ 是求解最大公因数带来的。
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef unsigned __int128 ll;
constexpr const int N=1e5,M=10,D=5;
//正分数
ll gcd(ll a,ll b){
while(b){
ll tmp=b;
b=a%b;
a=tmp;
}
return a;
}
ll lcm(ll a,ll b){
return a/gcd(a,b)*b;
}
struct frac{
ll p,q;
frac(){
q=1,p=0;
}
frac(ll x){
q=1,p=x;
}
frac(ll pp,ll qq){
p=pp,q=qq;
}
};
frac operator +(frac a,frac b){
frac c;
c.q=lcm(a.q,b.q);
c.p=a.p*c.q/a.q+b.p*c.q/b.q;
ll pl=gcd(c.p,c.q);
c.p/=pl;
c.q/=pl;
return c;
}
frac operator +=(frac &a,frac b){
return a=a+b;
}
frac operator /(frac a,ll b){
a.q*=b;
ll pl=gcd(a.p,a.q);
a.p/=pl;
a.q/=pl;
return a;
}
int n,m;
struct node{
int d;
int a[D+1];
frac value;
}a[N+1];
void topSort(){
static int in[N+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=a[i].d;j++){
in[a[i].a[j]]++;
}
}
queue<int>q;
for(int i=1;i<=n;i++){
if(!in[i]){
q.push(i);
}
}
while(q.size()){
int x=q.front();q.pop();
frac add=a[x].value/a[x].d;
for(int i=1;i<=a[x].d;i++){
a[a[x].a[i]].value+=add;
if(--in[a[x].a[i]]==0){
q.push(a[x].a[i]);
}
}
}
}
void Write(ll x){
static char s[101]={};
int top=0;
do{
s[++top]=x%10^'0';
x/=10;
}while(x);
while(top){
cout<<s[top--];
}
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i].d;
for(int j=1;j<=a[i].d;j++){
cin>>a[i].a[j];
}
}
for(int i=1;i<=m;i++){
a[i].value=1;
}
topSort();
for(int i=1;i<=n;i++){
if(!a[i].d){
Write(a[i].value.p);
cout<<' ';
Write(a[i].value.q);
cout<<'\n';
}
}
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
