这张图有几块,各多大
七个点的图。运行下面这段程序:
def blocks(g):
seen = set()
out = []
for s in sorted(g):
if s in seen:
continue
blk = []
st = [s]
seen.add(s)
while st:
u = st.pop()
blk.append(u)
for v in g[u]:
if v not in seen:
seen.add(v)
st.append(v)
out.append(sorted(blk))
return out
g = {0: [1, 2], 1: [0, 3], 2: [0, 4],
3: [1, 4], 4: [2, 3], 5: [6], 6: [5]}
b = blocks(g)
print(str(len(b)) + "/" + "/".join(str(len(x)) for x in b))
全部评论