Python选手11RE1AC:请调高递归层数限制
查看原帖
Python选手11RE1AC:请调高递归层数限制
1319292
candysad楼主2024/12/3 03:44
# 修改递归深度限制
import sys 
sys.setrecursionlimit(100000)

from collections import defaultdict
from math import inf

line = input()
n, m = [int(c) for c in line.split()]

edges = []
for _ in range(m):
    line = input()
    a, b = [int(c) for c in line.split()]
    edges.append((a, b))

def TarjanPoints(n, edges):
    g = [[] for _ in range(n)]
    for a, b in edges:
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)

    points = set()
    vis = defaultdict(lambda:inf)
    low = defaultdict(lambda:inf)
    step = 0
    
    def dfs(node, pre):
        nonlocal step
        vis[node] = step
        low[node] = step
        step += 1

        child = 0 # 相互分离的子节点数目,这些子节点不在相同的环上
        for next in g[node]:
            if next == pre:
                continue
            elif next not in vis:
                child += 1
                dfs(next, node)
                low[node] = min(low[node], low[next])

                if node != pre and low[next] >= vis[node]:
                    points.add(node)
            else:
                low[node] = min(low[node], vis[next])
        if node == pre and child > 1:
            points.add(node)

    for start in range(n):
        if start not in vis:
            dfs(start, start)
                      
    return points

result = TarjanPoints(n, edges)
result = sorted(result)
print(len(result))
for node in result:
    print(node + 1, end=' ')
2024/12/3 03:44
加载中...