这两对点连得通吗
问两件事:0 号和 5 号连不连通?1 号和 3 号呢?运行下面这段程序:
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)
def same(x, y):
return any(x in blk and y in blk for blk in b)
print(str(same(0, 5)) + "/" + str(same(1, 3)))
全部评论