[Python 3] BOJ 11266: 단절점

 

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

 

Articulation Point (단절점)을 이용해서 풀어야 하는 문제였다.

DFS를 응용하여 풀이할 수 있었다.

 

타 블로그들에서도 잘 설명이 되어 있지만, 간단하게 설명해보겠다.

 

현재 위치해있는 정점 A 보다 늦게 탐색이 될 예정인 정점들 중에서 정점 A보다 먼저 탐색이 되는 정점으로 가는 경로가 없을 경우에 정점 A를 단절점이라고 할 수 있다.

그리고, 예외적인 케이스로서 루트 노드로 시작한 노드의 자식의 수가 2개 이상이면 단절점이라고 할 수 있다.

 

방문하지 않은 정점으로 이동을 할 경우에는, 반복적으로 dfs를 진행하여, 제일 정점의 방문 순번이 낮은 경우를 visited에 저장한다고 생각하면 된다.

import sys
input=sys.stdin.readline
sys.setrecursionlimit(int(1e5))
def dfs(curr,isroot):
    global nodecount
    nodecount+=1
    visited[curr]=nodecount
    currval=visited[curr]
    child=0
    for next in data[curr]:
        if not visited[next]:
            child+=1
            minchild=dfs(next,0)
            if not isroot and minchild>=visited[curr]:
                cut[curr]=1
            currval=min(currval,minchild)
        else:
            currval=min(currval,visited[next])
    if isroot and child>1:
        cut[curr]=1
    return currval
v,e=map(int,input().split())
data=list(list() for _ in range(v+1))
visited=[0 for _ in range(v+1)]
cut=list(0 for _ in range(v+1))
nodecount=0
for _ in range(e):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
for i in range(1,v+1):
    if not visited[i]:
        dfs(i,1)
print(sum(cut))
for i in range(1,v+1):
    if cut[i]:
        print(i,end=" ")