只WA了一个点有大佬帮看看嘛~
查看原帖
只WA了一个点有大佬帮看看嘛~
281217
jon666楼主2020/10/29 23:17
#!python3.7

import sys
sys.setrecursionlimit(999999999)


def get_input():
    edges = []
    try:
        input()
    except:
        pass
    while True:
        try:
            line = input().strip().split(' ')
        except:
            break
        u, v = line[0], line[1]
        edges.append((u, v))
    return edges


def general_tarjan(adj, root):
    dfn, low, p = dict(), dict(), dict()

    def dfs(u):
        dfn[u] = len(dfn)
        tmp_low = dfn[u]
        for v in adj[u]:
            if v in dfn and v != p[u]:
                tmp_low = min(tmp_low, dfn[v])
        for v in adj[u]:
            if v not in dfn:
                p[v] = u
                dfs(v)
                tmp_low = min(tmp_low, low[v])
        low[u] = tmp_low

    dfs(root)
    return p, dfn, low


def edges_to_list(edges):
    adj = {}
    for u, v in edges:
        if u not in adj:
            adj[u] = set()
        if v not in adj:
            adj[v] = set()
        adj[u].add(v)
        adj[v].add(u)
    return adj


def cut_vertex(edges):
    root = edges[0][0]
    counter = 0
    graph = edges_to_list(edges)
    p, dfn, low = general_tarjan(graph, root)
    result = set()
    for y in p:
        x = p[y]
        if x == root:
            counter += 1
            if counter == 2:
                result.add(root)
        elif dfn[x] <= low[y]:
            result.add(x)
    return result


def cut_edge(edges):
    root = edges[0][0]
    graph = edges_to_list(edges)
    p, dfn, low = general_tarjan(graph, root)
    result = []
    for x in p:
        if dfn[p[x]] < low[x]:
            result.append((p[x], x))
    return result


edges = get_input()
nodes = cut_vertex(edges)
nodes = [ int(i) for i in nodes ]
nodes.sort()
nodes = [ str(i) for i in nodes ]

print(len(nodes))
print(' '.join(nodes))

2020/10/29 23:17
加载中...