단절점(Cut Vertex, Articulation Point)과 단절선(Bridge)

여기, 여기 참조, 강한연결요소(SCC)의 타잔 알고리즘과 관련있다.

단절점

한덩이의 무방향 그래프에서 한 정점을 제거했을 때 그래프가 두개 이상으로 나누어지면 단절점이라고 한다.

위 그래프에서 빨간정점들은 단절점이 된다. 따라서 개념은 무척쉽다.

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

보통 나이브 하지 않은 구현은 O(V+E)의 복잡도를 가지는데, 여기가 가장 이해하는데 도움이 됐다.

그 알고리즘을 살펴보면, 각 정점에 대해서 DFS트리를 만들면서, 다음 두가지를 기록한다.

1. 해당 정점을 방문한 순서: 이를 ord이라고 하자.

2. 해당 정점을 루트로 하는 서브트리로 부터 연결된 정점중 가장 작은 ord 값: 이를 low라고 하자.

그다음 해당 정점을 리턴하기전에 ord와 low를 비교해서 low가 ord보다 작으면 우회경로가 존재하므로 단절점이 아닌것으로 판단.

예를 들어 아래와 같은 그래프가 있을때

먼저 DFS트리를 그려보면 다음과 같다.(트리는 방향그래프가 아니나 이해를 위해 방향그래프로 표했다. 역방향 화살표가 하나있는데 이는 물론 트리의 구성요소는 아니고 back edge이다.)

괄호안의 숫자두개는 (ord, low)가 된다.

edge(u, v)가 아래방향 화살표인 tree edge라면, low[u] = min(low[u], low[v])가 되고,

edge(u, v)가 위쪽방향 화살표인 back edge라면, low[u] = min(low[u], ord[v])가 된다.

(이규칙에 맞는지 위의 그림을 잘 살펴보자)

말단노드가 아니면서 ord <= low 이면 단절점이므로 위 그래프에서는 단절점은 1, 6, 7이다.

(루트의 경우는 자식 노드가 2개 이상인지로 별도 판단)

근데, 실제로는 ord[n], low[n]을 다 구한다음에 후처리로 단절점을 판단하면 아래와 같은 반례때문에 잘되지 않았다(4번 노드가 문제인데 low[4]값은 최종적으로 1이 된다. 그러므로 후발적으로 ord <= low를 판단하면 단절점이 아닌것으로 판단된다)

그래서 low[n]을 최종판단하기전에 중간과정에서 자식노드중 하나라도 ord <= 자식트리의 low 인 순간에 즉발적으로 단절점을 판단해줘야했다. 자세한 사항은 아래 코드를 참조하자.이 문제의 답안이기도 하다.

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
using vi = vector<int>;
using vvi = vector<vi>;
 
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int V,E;cin>>V>>E;
    vvi adj_list(V + 1);
    REP(i, E)
    {
        int A,B;cin>>A>>B;
        adj_list[A].push_back(B);
        adj_list[B].push_back(A);
    }
    set<int> ans;
    //아래에서 visit는 ord와 통합가능하지만, 가독성을 위해 남겨둠
    vi visit(V + 1), ord(V + 1), parent(V + 1), root(V + 1); int g_ix = 0;
    function<int(int, int)> dfs = [&](int n, int par)-> int  // low를 리턴
    {
        visit[n] = 1;
        ord[n] = ++g_ix;
        int low = ord[n];
        int child = 0;
        for (auto adj : adj_list[n])
        {
            if (adj == par) continue;
            if (visit[adj])  // 백엣지의 경우
                low = min(low, ord[adj]);  // 접근가능한 back정점의 순서로 업데이트
            else {  // 트리엣지의 경우
                child++;
                int r = dfs(adj, n);  
                // 루트가 아니고 자식트리중 하나라도 자신위로 올라가지 못하면
                if(par!=-1 && r>=ord[n])  
                {
                    // 전체 자식노드를 보는게 아니라 즉발기로 동작함에 유의
                    // 주의할점은 현재 정점의 low값을 최종결정하기전에
                    // 단절점 판정이 이루어지는 부분
                    ans.insert(n);
                }
                low = min(low, r);
            }
        }
        // 루트이고 자식이 2개이상이면
        if (par == -1 && child > 1) ans.insert(n);
        return low;
    };
    REP1(i, V)if (visit[i] == 0)dfs(i, -1), root[i] = 1;
    cout << (int)ans.size() << endl; 
    for (auto a : ans) cout << a << ' ';
    cout << endl;
    return 0;
}

단절선

단절점 소스코드와 개념을 거의 그대로 활용할 수 있고, 아래 두가지 부분만 다르다.

1. 루트노드란 개념이 사라진다.

2. r >= ord[n] 조건이 r>ord[n] 으로 등호가 하나 사라진다.

2번에 대해서는 예제 입력인 아래 그래프에서  1번(루트) 정점을 기준으로 생각하면 등호인경우 사이클이 생겨서 단절선이 아님을 확인할 수 있다.(아래 그림 참조)

여기를 보면 해당 고민을 나보다 깊게 한 다른 블로그 포스팅을 볼 수 있다.

소스코드는 아래와 같고, 이 문제의 답안이기도 하다.

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
using vi = vector<int>;
using vvi = vector<vi>;
 
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int V, E; cin >> V >> E;
    vvi adj_list(V + 1);
    REP(i, E)
    {
        int A, B; cin >> A >> B;
        adj_list[A].push_back(B);
        adj_list[B].push_back(A);
    }
    set<pair<int, int>> ans;
    //아래에서 visit는 ord와 통합가능하지만, 가독성을 위해 남겨둠
    vi visit(V + 1), ord(V + 1), parent(V + 1), root(V + 1); int g_ix = 0;
    function<int(int, int)> dfs = [&](int n, int par)-> int  // low를 리턴
    {
        visit[n] = 1;
        ord[n] = ++g_ix;
        int low = ord[n];
        for (auto adj : adj_list[n])
        {
            if (adj == par) continue;
            if (visit[adj])  // 백엣지의 경우
                low = min(low, ord[adj]);  // 접근가능한 백정점 순서로 업데이트
            else {  // 트리엣지의 경우
                int r = dfs(adj, n);
                // 자식트리중 하나라도 자신위로 올라가지 못하면
                if (r > ord[n])  // 단절점 케이스와 다르게 r == ord[n]인 경우 그려보면 사이클로 인해 단절선이 아님을 알 수 있다.
                {
                    // 전체 자식노드를 보는게 아니라 즉발기로 동작함에 유의
                    // 주의할점은 현재 정점의 low값을 최종결정하기전에
                    // 단절점 판정이 이루어지는 부분
                    ans.insert({ min(n,adj), max(n,adj) });  // 문제 조건에 따라 순서 조정
                }
                low = min(low, r);
            }
        }
        // 단절선에서 루트정점이란 개념은 빠진다.
        // if (par == -1 && child > 1) ans.insert(n);
        return low;
    };
    REP1(i, V)if (visit[i] == 0)dfs(i, -1), root[i] = 1;
    cout << (int)ans.size() << '\n';
    for (auto a : ans) cout << a.first << ' ' << a.second << '\n';
    return 0;
}