五项一起对得上吗
运行下面这段程序:
def dfs(g, s):
seen = set()
out = []
def go(u):
seen.add(u)
out.append(u)
for v in g[u]:
if v not in seen:
go(v)
go(s)
return out
from collections import deque
def bfs(g, s):
seen = {s}
q = deque([s])
out = []
while q:
u = q.popleft()
out.append(u)
for v in g[u]:
if v not in seen:
seen.add(v)
q.append(v)
return out
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
from collections import deque
def dist(g, s):
d = {s: 0}
q = deque([s])
while q:
u = q.popleft()
for v in g[u]:
if v not in d:
d[v] = d[u] + 1
q.append(v)
return [d.get(i, -1) for i in sorted(g)]
from collections import deque
def kahn(g):
d = {u: 0 for u in g}
for u in g:
for v in g[u]:
d[v] += 1
q = deque(sorted(u for u in g if d[u] == 0))
out = []
while q:
u = q.popleft()
out.append(u)
for v in g[u]:
d[v] -= 1
if d[v] == 0:
q.append(v)
return out
g = {0: [1, 2], 1: [0, 3], 2: [0, 4],
3: [1, 4], 4: [2, 3], 5: [6], 6: [5]}
ok = (dfs(g, 0) == [0, 1, 3, 4, 2]
and bfs(g, 0) == [0, 1, 2, 3, 4]
and len(blocks(g)) == 2
and dist(g, 0)[4] == 2
and len(kahn({0: [2], 1: [2], 2: [3, 4], 3: [5], 4: [5], 5: []})) == 6)
print(ok)
全部评论