[Algorithm] How To Find Articulation Point with DFS

DFS Tree의 성질을 이용하여 Articulation Point를 찾기

DFS Tree의 성질과 Articulation Point(단절점)의 정의를 활용하여 Graph에서 Articulation Point(단절점)를 찾아보자.

Definition of Articulation Point

단절점의 정의 : 어떤 Graph G에 속하는 vertex v에 대하여 vertex v와 vertex v와 incident한(edge의 구성요소로 v를 가지고 있는) edge를 G에서 제거했을 때, G가 disconnected 된다면 vertex v는 G의 Articulation Point가 된다,

*Definition of Connected G : G에 속하는 임의의 vertex v, w에 대하여 v에서 w가 reachable 하고 w에서 v가 reachable 하면 G는 connected 하다.

How to Find Articulation Point

> 보조정리1. DFS Tree에서 Root Node의 Child Node의 개수가 2개 이상이면 그 Root Node는 Articulation Point이다. (필요충분조건)

proof

i) -> 방향 증명
--> Contradiction(귀류법). 만약 Root Node가 Articulation Point가 아니라면 Graph G에서 Root Node를 제거한 G가 connected여야 한다. 그러나 DFS Tree에서는 Cycle이 존재하지 않으므로 (by Def of DFS Tree) 모순!

ii) <- 방향 증명
--> Contradiction. Child Node의 개수가 1개 이하라면 Root Node를 제거한 Graph G가 Connected이므로 Root Node가 Articulation Point라는 가정에 모순!

 

보조정리2. Non-Root Node인 Graph G에 속하는 임의의 vertex v와 v의 1) Child Node가 u일 때 2) descendant u와 v의 proper Ancestor간 edge가 없으면 v는 Articulation Point. (필요충분조건)

proof

i) -> 방향 증명
Contradiction. v가 Articulation Point가 아니라면, u의 descendant를 포함하는 subtree와 v의 proper Ancestor가 Connected여야하는데 둘 사이에 edge가 없으므로 모순!

ii) <- 방향 증명
Contradiction. V가 Articulation Point임에도 불구하고 v의 proper Ancestor와 v의 child node u의 descendant u사이에 edge가 존재하면 v를 뺀 G는 connected이므로 모순!

key lemma 3: leaf Node는 Aritculation Point가 될 수 없다.

proof

DFS Tree상에서 leaf Node와 incident한 backEdge가 존재하지 않을 때, leaf Node를 제거하더라도 여전히 남아있는 그래프 G는 Connected하다.

이 세가지 정리를 이용하여 그래프 G에 속하는 Vertex들이 Articulation Point인지 판단해주면 된다.

이것을 의사코드로 나타내면 다음과 같다.

### Pseudo Code
#pre[v] : v를 첫 방문한 순서
#low[v] : v의 descendant u(u=v일 수 있음)와 incident한 Back-Edge (u,w)가 존재할 경우 low[v] = min(pre[u], pre[w])로 정의
ArticulationPoint = [False for _ in range(V+1)]

counter = 1 #첫 방문 순서와 방문을 완료한 순서를 기록하기 위한 global변수

def DFS(v, parent of v, root Node)
	visited[v] = True
    pre[v] = low[v] = counter++
    children = 0
    
    for u in graph[v]:
    	if visited[u] and u != parent of v:
        	low[v] = min(low[v], pre[u]) #(v에서 u로의 Back-Edge가 존재할 때)
            
        else:
        	DFS(u, v, root Node)
            low[v] = min(low[v], low[u])
            if low[u] >= low[v] and v != Root Node:
            	ArticulationPoint[v] = True
        		children += 1
                
    if v == root Node and children > 1:
    	Articulation[v] = True

연관문제

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

답안 예시

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

def explore(graph, v, visited, r, root):
    global counter
    children = 0
    visited[v] = True
    pre[v] = counter
    low[v] = counter
    counter = counter + 1

    for i in graph[v]:
        if (visited[i]):
            if (r != i): #BackEdge에 대해서만 low 갱신할 수 있도록 parent의 pre는 배제
                low[v] = min(low[v], pre[i])
        else:
            explore(graph, i, visited, v, root)
            low[v] = min(low[v], low[i])
            if (low[i] >= pre[v]):
                if (v != root):
                    cutPoint[v] = True
            children += 1

    if (r==0 and (children>1)):
        cutPoint[v] = True



V, E = map(int, input().split())
graph = [ [] for i in range(V+1) ]
visited = [False for _ in range(V+1)]
cutPoint = [False for _ in range(V+1)]
pre = [0 for i in range(V+1)]
low = [0 for i in range(V+1)]

counter = 1

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

for i in range(1, V+1):
    root = i
    explore(graph, i, visited, 0, root)


ans = ''
cnt = 0
for i in range(1, V+1):
    if (cutPoint[i] == True):
        cnt += 1
        ans += f'{i} '
print(cnt)
if cnt:
    print(ans)