[백준] 11266 - 단절점 (Python)

주어지는 그래프를 루트에서 시작해 중복 없이 재귀적으로 순회한다고 생각해보자. 이때 각 노드에 진입하는 순서에 따라 번호를 부여한다.

한 노드를 기준으로 했을 때, 특정 자식이 도달가능한 진입순서의 최솟값이 해당 노드의 진입순서보다 앞선다면 해당 자식으로 통하는 다른 경로가 있다는 것을 알 수 있다.

예외적으로 루트의 경우는 진입 가능한 자식이 하나일 경우 루트를 제거해도 그래프가 나누어지지 않는다. 따라서 진입 가능한 자식이 둘 이상인 경우에만 단절점이 된다.

주어지는 그래프가 연결 그래프가 아닐 가능성이 있음을 고려하여 모든 노드를 검사해야 한다.

import sys
sys.setrecursionlimit(10**4+100)
input = sys.stdin.readline

def dfs(node, is_root):
	# 0번 인덱스는 카운트로 사용
    visit_order[0] += 1
    visit_order[node] = visit_order[0]
    child_cnt = 0
    # 최소 진입순서
    min_order = visit_order[node]
    for child in graph[node]:
    	# 이전에 방문한 노드라면 최소 진입순서만 업데이트
        if visit_order[child]:
            min_order = min(min_order, visit_order[child])
            continue
        child_cnt += 1
        res = dfs(child, False)
        min_order = min(min_order, res)
        # 루트노드가 아니고 해당 자식의 최소 진입순서가 같거나 뒤인 경우 현재 노드는 단절점
        if not is_root and res >= visit_order[node]:
            artic_point[node] = 1
    # 만약 루트노드이고 진입가능 자식이 둘 이상인 경우
    if is_root and child_cnt >= 2:
        artic_point[node] = 1
    # 도달가능한 최소 진입순서를 반환
    return min_order
    
v, e = map(int, input().rstrip().split())

graph = [[] for _ in range(v+1)]
visit_order = [0]*(v+1)
artic_point = [0]*(v+1)

for _ in range(e):
    a, b = map(int, input().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

count = 0
answer = []
# 연결 그래프가 아닐 가능성이 있음
for i in range(1, v+1):
    if not visit_order[i]:
        dfs(i, True)
  	# 단절점 저장
    if artic_point[i]:
        count += 1
        answer.append(i)

print(count)
if count > 0:
    print(*answer)