그래프에서 $O(N+M)$에 단절점 찾기¶
무방향 그래프가 주어집니다. 단절점(또는 절단 정점)은 연결된 간선들과 함께 제거했을 때 그래프가 끊어지게 되는(더 정확히는 그래프의 연결 요소 개수가 늘어나는) 정점으로 정의됩니다. 목표는 주어진 그래프의 모든 단절점을 찾는 것입니다.
여기서 설명하는 알고리즘은 깊이 우선 탐색에 기반하며 $O(N+M)$의 복잡도를 가집니다. 여기서 $N$은 그래프의 정점 개수이고 $M$은 간선 개수입니다.
알고리즘¶
그래프의 임의의 정점 $root$를 골라 그 정점에서 깊이 우선 탐색을 실행하십시오. 다음 사실에 주목하십시오(증명하기 쉽습니다):
-
DFS 도중 정점 $v\ne root$에서 시작하는 간선들을 살펴보고 있다고 합시다. 현재 간선 $(v, to)$에 대해 정점 $to$와 DFS 탐색 트리에서 그 자손들 중 어느 것도 $v$의 조상으로 가는 역방향 간선을 가지지 않는다면, $v$는 단절점입니다. 그렇지 않으면 $v$는 단절점이 아닙니다.
-
남은 경우인 $v=root$를 살펴봅시다. 이 정점은 DFS 트리에서 자식이 둘 이상일 때, 그리고 그때에만 단절점이 됩니다.
이제 각 정점에 대해 이 사실을 효율적으로 확인하는 방법을 익혀야 합니다. 깊이 우선 탐색으로 계산한 "노드 진입 시각"을 사용하겠습니다.
그러면 $tin[v]$를 노드 $v$의 진입 시각이라고 합시다. 각 정점 $v$에 대해 이 사실을 확인할 수 있게 해 주는 배열 $low[v]$를 도입합니다. $low[v]$는 $tin[v]$, 역방향 간선 $(v, p)$로 노드 $v$와 연결된 각 노드 $p$의 진입 시각 $tin[p]$, 그리고 DFS 트리에서 $v$의 직계 자손인 각 정점 $to$의 $low[to]$ 값 중 최솟값입니다:
이제 정점 $v$ 또는 그 자손 중 하나에서 $v$의 조상 중 하나로 가는 역방향 간선이 존재하는 것은, 정점 $v$가 $low[to] < tin[v]$를 만족하는 자식 $to$를 가질 때이며 오직 그때뿐입니다. $low[to] = tin[v]$이면 역방향 간선은 $v$로 직접 이어지고, 그렇지 않으면 $v$의 조상 중 하나로 이어집니다.
따라서 DFS 트리의 정점 $v$는 $low[to] \geq tin[v]$일 때, 그리고 그때에만 단절점입니다.
구현¶
구현에서는 세 가지 경우를 구별해야 합니다: DFS 트리에서 간선을 따라 내려갈 때, 정점의 조상으로 가는 역방향 간선을 찾았을 때, 그리고 정점의 부모로 되돌아갈 때입니다. 각 경우는 다음과 같습니다:
- $visited[to] = false$ - 이 간선은 DFS 트리의 일부입니다;
- $visited[to] = true$ && $to \neq parent$ - 이 간선은 조상 중 하나로 가는 역방향 간선입니다;
- $to = parent$ - 이 간선은 DFS 트리에서 부모로 되돌아가는 간선입니다.
이를 구현하려면 현재 노드의 부모 정점을 인자로 받는 깊이 우선 탐색 함수가 필요합니다.
int n; // number of nodes
vector<vector<int>> adj; // adjacency list of graph
vector<bool> visited;
vector<int> tin, low;
int timer;
void dfs(int v, int p = -1) {
visited[v] = true;
tin[v] = low[v] = timer++;
int children=0;
for (int to : adj[v]) {
if (to == p) continue;
if (visited[to]) {
low[v] = min(low[v], tin[to]);
} else {
dfs(to, v);
low[v] = min(low[v], low[to]);
if (low[to] >= tin[v] && p!=-1)
IS_CUTPOINT(v);
++children;
}
}
if(p == -1 && children > 1)
IS_CUTPOINT(v);
}
void find_cutpoints() {
timer = 0;
visited.assign(n, false);
tin.assign(n, -1);
low.assign(n, -1);
for (int i = 0; i < n; ++i) {
if (!visited[i])
dfs (i);
}
}
주 함수는 find_cutpoints입니다. 이 함수는 필요한 초기화를 수행하고 그래프의 각 연결 요소에서 깊이 우선 탐색을 시작합니다.
함수 IS_CUTPOINT(a)는 정점 $a$가 단절점이라는 사실을 처리하는 함수로, 예를 들어 그 정점을 출력합니다(한 정점에 대해 여러 번 호출될 수 있으니 주의하십시오).