[알고리즘] 단절점(Articulation Points or Cut Vertices)

단절점이란 무방향 그래프에서 해당 정점을 제거했을 때 그래프가 두 개 이상으로 나누어질 때 그 정점을 단절점이라고 합니다.

 

먼저 간단하게 생각할 수 있는 방법은 모든 정점에 대해서 정점 하나를 삭제해보고 DFS를 돌려서 그래프의 개수를 세보면 됩니다. 이때 시간 복잡도는 정점의 개수를 V, 간선의 개수를 E라고 할 때 O(V * (V + E) )가 됩니다.

 

그러나 위 방식은 비효율적이고 O(V + E) 시간복잡도로 단절점을 구할 수 있는 방법이 있습니다.

 

바로 DFS spanning tree를 이용하는 방법입니다.

 

위와 같은 그래프가 있을 때 DFS spanning tree로 번호를 매겨보겠습니다.

DFS spanning tree에서 단절점을 찾는 방법은

정점 A에서 부모 노드를 제외한 자식 노드들이 역방향 간선(backward edge)을 통해서 정점 A보다 위에 있는 선조로 갈 수 없으면 정점 A는 단절점이 됩니다.

 

6번 정점을 예로 들면

정점 6에서 부모 노드 1을 제외한 자식 노드인 7이 역방향 간선을 통해서 정점 6보다 위에 있는 선조 1로 갈 수 없으니깐 정점 6은 단절점이 됩니다.

 

2번 정점을 예로 들면

정점 2에서 부모 노드 7을 제외한 자식노드인 3이 역방향 간선을 통해서 정점 2보다 위에 있는 선조 7로 갈 수 있으니 정점 2는 단절점이 아닙니다.

 

그런데 루트 노드의 경우엔 선조가 없기 때문에 예외가 발생합니다.

루트 노드일 땐 루트의 자식 노드의 개수를 계산해서 자식 노드 수가 2 이상일 때 단절점이라고 판단하면 됩니다.

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
using namespace std;
 
int v, e;
 
vector<int> adj[10001];
int visited[10001];
bool cutVertex[10001];
int num = 1;/*정점 A가 우회로를 통해서 갈 수 있는 가장 빠른 정점을 리턴*/
int dfs(int A, int parent, bool isRoot) {
    visited[A] = num++;
    int child = 0;
    int ret = visited[A]; //처음엔 자기 자신이 최상위 노드
    for (auto& next : adj[A]) {
        if (next == parent) continue; //부모를 제외
        if (visited[next]) {
            ret = min(ret, visited[next]); // 우회로 갱신
            continue;
        }
        child++;
        int low = dfs(next, A, false);// 자식 노드가 우회로를 통해서 갈 수 있는 가장 빠른 정점
 
        if (!isRoot && low >= visited[A]) { //자식 노드가 정점 A보다 위에 있는 선조로 갈 수 없으면
            cutVertex[A] = true; // 단절점
        }
        ret = min(ret, low); //정점 A가 갈 수 있는 선조 업데이트
    }
    if (isRoot) {
        cutVertex[A] = child >= 2 ? true : false;
    }
    return ret;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> v >> e;
    for (int i = 0; i < e; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 1; i <= v; i++) {
        if (!visited[i]) {
            dfs(i, 0, true);
        }
    }
    int cnt = 0;
    for (int i = 1; i <= v; i++) {
        if (cutVertex[i]) cnt++;
    }
    cout << cnt << '\n';
    for (int i = 1; i <= v; i++) {
        if (cutVertex[i]) cout << i << ' ';
    }
 
    return 0;
}

 

<백준 문제>

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

11266번: 단절점