[python] 백준 11266 단절점

https://www.acmicpc.net/problem/11266

 

문제 해결

• 단절점이란?
  • 정점을 제거했을 때 그래프가 두 개 이상으로 나누어지는 정점, 즉 없으면 두개의 그래프로 나누어진다고 생각
  • 단순 사이클을 이루는 점이거나 직선 그래프를 잇는 점이 아닌 여러 노드들을 잇는 교차로 점들을 단절점이라 생각하면 된다.
• 풀이는 이해가 쉽지만 바로 풀기는 쉽지 않은 문제...

 

CODE

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)


def dfs(node, is_root):
    visit_order[0] += 1 # visit 번호
    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

if __name__ == "__main__":
    v, e = map(int, input().split())
    graph = [[] for _ in range(v+1)]
    visit_order = [0 for _ in range(v+1)] # 최소 사이클 그룹
    artic_point = [0 for _ in range(v+1)] # 단절점

    for _ in range(e):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    cnt = 0
    answer = []
    for i in range(1, v+1):
        if not visit_order[i]: # 그룹에 속해있지 않으면
            dfs(i, True) # 그 번호를 root로 사이클 조사 시작
        if artic_point[i]: # 단절점이면
            cnt += 1
            answer.append(i)
    print(cnt)
    if cnt >0:
        print(*answer)