有几个分量,最大的那个多大
还是那七个点,这次把 5 → 3 那条边加回来,于是图里有了环:
G = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (5, 3), (4, 6)]
N = 7
def build(edges):
g = {u: [] for u in range(N)}
for a, b in edges:
g[a].append(b)
for u in g:
g[u].sort()
return g
def kosaraju(edges, second_reversed=True):
g = build(edges)
rg = build([(b, a) for a, b in edges])
seen, order = set(), []
for s in range(N):
if s in seen:
continue
st = [(s, iter(g[s]))]
seen.add(s)
while st:
u, it = st[-1]
for v in it:
if v not in seen:
seen.add(v)
st.append((v, iter(g[v])))
break
else:
order.append(u)
st.pop()
second = rg if second_reversed else g
seen2, groups = set(), []
for s in reversed(order):
if s in seen2:
continue
st, grp = [s], []
seen2.add(s)
while st:
u = st.pop()
grp.append(u)
for v in second[u]:
if v not in seen2:
seen2.add(v)
st.append(v)
groups.append(sorted(grp))
return sorted(groups)
gs = kosaraju(G)
print(str(len(gs)) + "/" + str(max(len(x) for x in gs)))
全部评论