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

---

목차

1. 단절점(Articulation Point)이란?

2. 단절점 구하는 방법

3. 단절점 구현

4. 단절선 구현

5. 단절점 관련 문제

---

1. 단절점(Articulation Point)이란?

하나의 컴포넌트로 구성된 무방향 그래프에서 특정 정점을 제거 했을때 두개 이상의 컴포넌트(그래프)로 나눌 수 있는 그러한 정점을 단절점이라고 한다.

위의 그래프를 볼때 단절점은 아래 주황색 정점들이 될 것이다.

2번 정점으로 인해 1과 3,4,5,6,7,8 그래프 둘로 나뉘어지게 되고

4번 정점으로 인해 1,2,3과 5,6,7,8 그래프 둘로 나뉘어지게 되고

6번 정점으로 인해 1,2,3,4,5,8과 7 그래프 둘로 나뉘어지게 된다.

2. 단절점 구하는 방법

이제 단절점이 어떤 것인지 알게 되었으니 단절점을 구할 수 있어야 한다.

단절점을 가장 Naive하게 찾아 볼 수 있는 방법은 모든 정점을 한번씩 선택하여(V) 제거한 후 그래프가 나뉘어지는지 파악해보는 방법이 있다(V + E). 따라서 시간 복잡도는 O(V * (V + E))가 된다.

이렇게 한다면 시간 복잡도 면에서 너무 비효율적임을 누구든지 알 수 있다.

그렇다면 어떻게 단절점을 빠르게 구할 수 있을까?

우선 단절점의 특성에 대해 알아보자.

만약 특정 정점이 단절점이라면 단절점에 바로 인접해있는 정점들의 쌍은 단절점이 없으면 우회로로 인해 연결되어있지 않아야 한다.

 

만약 5번 정점이 단절점이라 생각해보자.

5번 정점에 바로 인접해있는 정점 6과 4는 서로 5가 없어도 우회로로인해 연결되어 있다.

따라서 5번 정점은 단절점이 될 수 없다.

이번에는 4번 정점이 단절점이라 생각해보자.

이때 2, 3번 정점은 서로가 경로를 이용하여 만날 수 있고 5, 8번 정점도 우회경로를 통해 서로 만날 수 있다.

하지만 2, 5 / 2, 8 / 3, 5 / 3, 8 정점들의 쌍은 서로 만날 수 없다.

따라서 4번 정점은 단절점이 된다.

이제 이 특성을 이용하여 단절점을 한번 구해보자.

우선 위와 같이 DFS를 이용하여 정점들의 방문 순서를 기록해주자.

아무 정점부터 시작해도 되지만 여기서는 최초 노드를 1번 노드로 잡고 시작하기에 1번이 방문 순서가 1이다.

이제 앞서 말했던 위의 특성을 사용해서 이 번호들을 어떻게 쓸지 생각해보자.

특정 A번 정점에서 자식 노드들이 정점 A를 거치지 않고 정점 A보다 빠른 방문번호를 가진 정점으로 갈 수 없다면 단절점이다.

위의 내용을 그림으로 생각해보자.

특정 A번 정점에서 자식 노드들이 정점 A를 거치지 않고 정점 A보다 빠른 방문번호를 가진 정점으로 갈 수 없다면 단절점이다.

특정 5번 정점에서 자식 노드들이 정점 5를 거치지 않고 정점 5보다 빠른 방문번호를 가진 정점으로 갈 수 없다면 단절점이다.

-> 6번 정점은 5번의 5번째 방문순서보다 빠른 4번째 방문 정점으로 갈 수 있으므로 5번은 단절점이 아니다.

특정 A번 정점에서 자식 노드들이 정점 A를 거치지 않고 정점 A보다 빠른 방문번호를 가진 정점으로 갈 수 없다면 단절점이다.

특정 4번 정점에서 자식 노드들이 정점 4를 거치지 않고 정점 4보다 빠른 방문번호를 가진 정점으로 갈 수 없다면 단절점이다.

-> 5,8번 정점은 4번의 4번째 방문순서보다 빠른 2,3번째 방문 정점으로 갈 수 없으므로 4번은 단절점이다.

이때 단절점의 한가지 예외가 있다.

루트 노드로 잡은 특정 노드의 자식 수가 2개 이상이면 무조건 단절점이다.

즉, 정리하자면 아래와 같다.

정점 A가 루트 라면 :: 

자식 수가 2개 이상이면 단절점이다.

정점 A가 루트가 아니라면 :: 

A번 정점에서 자식 노드들이 정점 A를 거치지 않고 정점 A보다 빠른 방문번호를 가진 정점으로 갈 수 없다면 단절점이다.

따라서 위의 방법은 이용하면 한번의 DFS로 답을 구할 수 있으니 O(N + M)의 시간 복잡도를 가지게 된다.

3. 단절점 구현

[11266번] 단절점 :: https://www.acmicpc.net/problem/11266 문제를 기준으로 작성하였습니다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<int> vc[10002];
int discovered[10002];
bool isCut[10002];
 
int number;
 
// here == 정점 A
int dfs(int here, bool isRoot)
{
    discovered[here] = ++number; // DFS 탐색 순서 지정
    int ret = discovered[here];
 
    int child = 0; // 자식 수 count
 
    for (int i = 0; i < vc[here].size(); i++)
    {
        int next = vc[here][i];
 
        /* 
         만약 이미 DFS에서 탐색된 정점이라면 
         현재 정점의 방문순서와 탐색된 정점의 방문 순서중 min값을 찾는다.
         이 방법을 이용해야 
         " A번 정점에서 자식 노드들이 정점 A를 거치지 않고 
         정점 A보다 빠른 방문번호를 가진 정점으로 갈 수 없다면 단절점이다. "
         를 찾을 수 있다.
        */
        if (discovered[next])
        {
            ret = min(ret, discovered[next]);
            continue;
        }
 
        child++;
        int prev = dfs(next, false);
 
        /*
            정점 A가 루트가 아니라면 ::
            A번 정점에서 자식 노드들이 정점 A를 거치지 않고 정점 A보다 빠른 방문번호를 가진 정점으로 갈 수 없다면 단절점이다.
        */
        if (!isRoot && prev >= discovered[here])
            isCut[here] = true;
 
        ret = min(ret, prev);
    }
 
    /*
        정점 A가 루트 라면 ::
        자식 수가 2개 이상이면 단절점이다.
    */
    if (isRoot)
        isCut[here] = (child >= 2);
 
    return ret;
}
int main()
{
    int V, E;
    scanf("%d %d", &V, &E);
    for (int i = 0; i < E; i++)
    {
        int from, to;
        scanf("%d %d", &from, &to);
 
        vc[from].push_back(to);
        vc[to].push_back(from);
    }
 
    for (int i = 1; i <= V; i++)
        if (!discovered[i])
            dfs(i, true);
 
    int cnt = 0;
    for (int i = 1; i <= V; i++)
        if (isCut[i])
            cnt++;
 
    printf("%d\n", cnt);
    for (int i = 1; i <= V; i++)
        if (isCut[i])
            printf("%d ", i);
 
    return 0;
}
 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

4. 단절선 구현

단절선은 단절점과 유사하다.

단절점과 같이 DFS를 이용하는 방식으로 A번째 정점에서 부모로 가는 간선이 아닌 간선 중에서 아직 방문안한 노드의 discover 번호가 현재 discover 번호보다 클 경우 단절선이 된다.

[11400번] 단절선 :: https://www.acmicpc.net/problem/11400 문제를 기준으로 작성하였습니다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<int> vc[100002];
int discovered[100002];
vector<pair<int, int> > isCut;
 
int number;
 
// here == 정점 A
int dfs(int here, int parent)
{
    discovered[here] = ++number; // DFS 탐색 순서 지정
    int ret = discovered[here];
 
    for (int i = 0; i < vc[here].size(); i++)
    {
        int next = vc[here][i];
 
        if (next == parent)
            continue;
 
        if (discovered[next])
        {
            ret = min(ret, discovered[next]);
            continue;
        }
 
        int prev = dfs(next, here);
 
        if (prev > discovered[here])
            isCut.push_back({ min(here, next), max(here, next) });
 
        ret = min(ret, prev);
    }
 
    return ret;
}
 
int main()
{
    int V, E;
    scanf("%d %d", &V, &E);
    for (int i = 0; i < E; i++)
    {
        int from, to;
        scanf("%d %d", &from, &to);
 
        vc[from].push_back(to);
        vc[to].push_back(from);
    }
 
    for (int i = 1; i <= V; i++)
        if (!discovered[i])
            dfs(i, 0);
 
    sort(isCut.begin(), isCut.end());
 
    printf("%d\n", isCut.size());
 
    for (int i = 0; i < isCut.size(); i++)
        printf("%d %d\n", isCut[i].first, isCut[i].second);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

5. 단절점/단절선 관련 문제

http://www.crocus.co.kr/search/%EB%8B%A8%EC%A0%88%EC%A0%90

http://www.crocus.co.kr/search/단절선