단절점(Articulation Point)와 단절선(Bridge)

하나의 컴포넌트로 이루어진 무방향 그래프에서 한 정점을 제거했을 때 그래프가 두개 이상의 컴포넌트로 나누어지는 정점을 단절점이라고 합니다.

다음과 같은 무방향 그래프가 있다고 해봅시다.

여기서 빨간색 테두리로 이루어진 정점들중 하나를 지울 경우 컴포넌트가 2개로 나누어지게 됩니다.

이러한 성질을 가지는 정점들을 단절점이라고 부릅니다. 

그러면 우리는 단절점을 어떤 방법으로 찾을 수 있을까요?

우선은 단절점을 찾기 위해서 우선 단절점이 가지는 특징을 알아야 됩니다.

아까의 그래프에서 단절점인 빨간정점에 연결된 정점들을 초록정점으로 색칠해봤습니다.

우리는 어떤 정점 A에 연결된 모든 정점들 중 두 정점들 간에 정점 A를 거치지않고 갈 수 있는 우회경로가 존재하지 않는 경우가 존재한다면 정점 A는 단절점으로 판단할 수 있습니다.

초록색 정점 중 최하단 정점에서 우측상단 정점으로 빨간색 정점을 거치지않는 우회경로는 존재하지 않으므로 빨간정점은 단절점이 됩니다.

그러나 무작정 모든 정점들에 대해 연결된 정점들간의 우회경로를 확인하는 방법은 시간이 매우 많이 소요될것이므로 우리는 DFS를 탐색할 때 생기는 DFS 스패닝 트리를 이용하여 단절점을 빠른시간내에 효과적으로 구해보도록 하겠습니다.

아까의 그래프에 정점들의 번호를 붙여봤습니다.

자 우리는 이제 1번 정점부터 시작하여 DFS를 이용하여 탐색을하여 탐색되는 순서대로 번호를 매겨보겠습니다.

자 이제 다음과 같은 그래프에서 현재 탐색하는 정점 A에서 연결된 정점들 중 정점 A보다 늦게 탐색되는 정점들에서 정점 A보다 먼저 탐색되는 정점으로 가는 경로가 없는 경우가 존재한다면 정점 A는 단절점이 됩니다.

예를 들자면 단절점인 4번 정점보다 늦게 탐색되는 정점인 5번 정점에서는 [1,2,3,7] 번 정점을 탐색 불가능 합니다.

우리는 이를 이용하여 DFS에서 탐색되는 순서대로 discover번호를 매겨주면서 아직 탐색이 안된경우 해당 정점에서 DFS를 탐색하여 나오는 정점 중 discover번호가 가장 적은 정점을 탐색이 된 경우는 그 정점의 discover 번호만 비교하면서 가장 작은 discover 번호가 나의 discover 번호보다 크거나 같다면 그 정점은 단절점이 됩니다.

이렇게 판별할 경우 예외로 처리해줘야 할 케이스가 있는데 그 경우는  루트가 되는 정점의 케이스입니다.

루트가 되는 정점은 자식이 2이상일 경우 단절점이 됩니다.

이해를 돕기 위하여 BOJ 11266 단절점 소스코드를 첨부하겠습니다.

#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX_N 10000
using namespace std;
int n, m, disc[MAX_N + 1], cut[MAX_N + 1], ans, d, a, b;
vector<vector<int>> vt;
int dfs(int here, bool r) {
    disc[here] = ++d;
    int ret = disc[here];
    int child = 0;
    for (int there : vt[here]) {
        if (!disc[there]) {
            child++;
            int df = dfs(there, 0);
            if (!r&&df >= disc[here]) 
                cut[here] = true;
            ret = min(ret, df);
        }
        else
            ret = min(ret, disc[there]);
    }
    if (r&&child > 1) 
        cut[here] = true;
    return ret;
}
int main() {
    scanf("%d%d", &n, &m);
    vt.resize(n + 1);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        vt[a].push_back(b);
        vt[b].push_back(a);
    }
    for (int i = 1; i <= n; i++)
        if (!disc[i])
            dfs(i, 1);
    for (int i = 1; i <= n; i++)
        if (cut[i])
            ans++;
    printf("%d\n", ans);
    for (int i = 1; i <= n; i++)
        if (cut[i])
            printf("%d ", i);
    return 0;
}

disc배열은 DFS탐색에 따른 방문순서가 되고 함수에서 ret값은 해당 정점에서 더 탐색 가능한 정점들에서 얻어오는 discover 값중에서 가장 작은 disc 값을 가지게 됩니다. 

우리는 이 ret값을 나의 disc값과 비교하여 단절점 여부를 판단할 수 있습니다. 

함수의 2번째 인자인 r이 true일 경우 루트노드라는 의미이며 이 경우에는 자식 수를 세어주어 단절점 여부를 판단해 줍니다.

자 이제 무방향 그래프에서 단절점을 찾을 수 있겠나요?

단절선은 단절점의 정의와 비슷하지만 정점이 아닌 간선을 제거하였을 경우 그래프가 두개 이상의 컴포넌트로 나누어지는 간선입니다.

그렇기 때문에 단절선을 구하는 알고리즘도 단절점을 구하는 알고리즘과 유사합니다.

이번에도 DFS 스패닝 트리를 이용하여 A번째 정점에서 부모로 가는 간선을 제외하고 나머지 간선에서 아직 방문안한 노드에서 얻어온 discover 번호가 나의 discover 번호보다 클 경우 단절선이 됩니다.  

이번에도 BOJ 11400 단절선 소스코드를 첨부하겠습니다.

#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX_N 100000
using namespace std;
int n, m, disc[MAX_N + 1], cut[MAX_N + 1], d, a, b;
vector<vector<int>> vt;
vector<pair<int, int>> res;
int dfs(int here, int par) {
    disc[here] = ++d;
    int ret = disc[here];
    int child = 0;
    for (int there : vt[here]) {
        if (there == par)
            continue;
        if (!disc[there]) {
            int df = dfs(there, here);
            if (df > disc[here])
                res.push_back({ min(here,there),max(here,there) });
            ret = min(ret, df);
        }
        else
            ret = min(ret, disc[there]);
    }
    return ret;
}
int main() {
    scanf("%d%d", &n, &m);
    vt.resize(n + 1);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        vt[a].push_back(b);
        vt[b].push_back(a);
    }
    for (int i = 1; i <= n; i++)
        if (!disc[i])
            dfs(i, 0);
    sort(res.begin(), res.end());
    printf("%d\n", res.size());
    for (auto x : res)
        printf("%d %d\n", x.first, x.second);
    return 0;
}

자 이제 우리는 단절점과 단절선을 DFS 한번으로 구할 수 있게됬습니다.

시간복잡도는 DFS의 시간복잡도인 O(N+M)이 되겠군요.

이제 단절점과 단절선을 이용하여 다양한 문제를 해결해봅시다.