五项一起对得上吗

👁️ 0 人浏览 💬 0 人评论 ❤️ 添加收藏

运行下面这段程序:

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)
提交你的答案
请登录后提交答案。
去登录
代码编辑器
Ctrl + Enter 运行
本次输入:
输出:

                        
👩‍🏫
AI
💬 题目评论

全部评论