这题的做法大家已经讲的很详细了我也没啥好讲的 qaq
比较无聊写了一份 Python 水了一发,供诸君笑谈。
```python
def gcd(x, y):
if y == 0:
return x
else:
return gcd(y, x % y)
def add(v, u):
_g = g[v] * g[u] * oud[u]
_f = f[u] * (_g // (g[u] * oud[u])) + f[v] * (_g // g[v])
d = gcd(_f, _g)
f[v] = _f // d
g[v] = _g // d
def toposort():
q = []
for i in range(m):
q.append(i)
f[i] = 1
for u in q:
for v in E[u]:
ind[v] = ind[v] - 1
add(v, u)
if ind[v] == 0:
q.append(v)
[n, m] = map(lambda x: int(x), input().split(' '))
E = [[] for i in range(n)]
oud = [0] * n
ind = [0] * n
f = [0] * n
g = [1] * n
for i in range(n):
a = list(map(lambda x: int(x), input().split(' ')))
oud[i] = a[0]
a = a[1:]
for v in a:
v = v - 1
E[i].append(v)
ind[v] = ind[v] + 1
toposort()
for i in range(n):
if oud[i] == 0:
print(f[i], g[i])
```