BCC(이중 연결 요소) 이쁘게 구현하기

이중 연결 요소를 제가 이해할 수 있도록 설명한 글이 없어서 조금 더 직관적인 방식으로 구현한 BCC에 대해 소개해보고자 합니다.

 

먼저, 알고리즘의 대략적인 설명은 이렇습니다.

1. 아무 정점에서 DFS 스패닝 트리를 구성한다.

2. 백엣지가 있는 경우, 양 끝점을 잇는 경로 위의 점들은 모두 같은 BCC에 포함되므로 묶어준다.

3. 2. 에서 중복 간선이 있는 경우를 예외 처리한다.

 

더 자세한 디테일들은 코드와 함께 설명하겠습니다.

 

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fastio; cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
const int mod=1e9+7, MOD=998244353, inf=2e17;

int N, M;
vector<int> lnk[101010];

int g[101010];
int Find(int x){return g[x]==x?x:g[x]=Find(g[x]);}
void Union(int a, int b){g[Find(a)]=Find(b);}

int P[101010];
void dfs(int p) {
    for (int i : lnk[p]) {
        if (P[i]==-1) P[i]=p, dfs(i);
        else if (P[i]==p) Union(i, p);
        else if (i!=P[p]) while (Find(p)!=Find(i)) Union(p, P[Find(p)]);
    }
}

signed main(){
    fastio;

    cin >> N >> M;
    for (int i=1; i<=N; i++) g[i]=i;
    for (int i=1; i<=M; i++) {
        int a, b; cin >> a >> b;
        lnk[a].push_back(b); lnk[b].push_back(a);
    }

    fill(P+2, P+N+1, -1);
    dfs(1);

    return 0;
}

 

Union-Find는 경로 압축을 기반으로 하며, Find(x)는 x가 속한 트리의 루트 노드를 반환합니다.

Union(a, b)를 호출하면 a가 속한 트리의 루트를 b가 속한 트리의 루트의 자식으로 추가합니다.

 

DFS 함수를 호출하며 BCC를 구성하는 동안, 다음의 성질이 항상 유지됩니다.

- Find(x)는 현재를 기준으로 x가 속한 BCC의 정점들 중 DFS 스패닝 트리 상에서 가장 높은 정점이다.

 

현재 방문한 정점을 p, 그와 연결된 정점을 i라고 해봅시다.

P[i] == -1 인 경우에는 i를 아직 방문하지 않았으므로, P[i]=p로 설정하고 DFS를 계속해서 진행합니다.

그렇지 않으면 i가 p의 조상이고 i - p를 연결하는 백엣지가 존재하거나, p가 i의 부모이고 i - p 사이에 중복 간선이 있거나, i가 p의 부모인 경우로 나눌 수 있습니다.

 

그 중 3번째 경우는 고려하지 않을 것입니다.(2번째 경우만 고려해도 충분함)

2번째 경우 i와 p를 같은 BCC로 묶어 줍니다.

1번째 경우 i와 p가 같은 BCC에 속하게 될 때까지 Find(p)와 그 부모를 같은 BCC로 묶어 줍니다.

 

DFS를 진행하며 위의 과정을 반복하면, dfs(1) 실행 이후 같은 BCC에 속하는 점들끼리 같은 Find(x) 값을 갖게 됩니다.