Biconnected Component

Biconnected Component (BCC)는 무방향 그래프에서, 다음 조건을 만족하는 정점의 부분집합을 말합니다.

 

1. 부분집합에서 어떤 정점 하나를 삭제하더라도, 남은 정점들은 서로 연결되어 있다.

2. 이 부분집합에 다른 정점들을 추가하더라도 1을 만족하지 않는다. (1번을 만족하는 최대 크기의 집합이다)

 

따라서 다음과 같은 무방향 그래프는,

 

다음과 같이 5개의 BCC로 분리됩니다.

그래프를 이와같이 BCC로 분리하여 하나의 BCC를 하나의 정점으로 대체하면 그래프를 트리로 나타낼 수 있게 됩니다.

 

일반적인 그래프를 트리로 바꾸고 나면 트리에만 사용할 수 있는 다양한 알고리즘을 사용할 수 있게 됩니다.

 

SCC를 먼저 보신분들은 알겠지만, SCC와 개념이나 코드가 거의 동일합니다.

SCC의 무방향 그래프 버전이라고 생각해도 좋습니다.

---

그러면 BCC를 구하는 방법에 대해 알아봅시다.

 

BCC에서는 한 정점이 여러 개의 BCC에 속할 수 있는 대신,

한 간선은 하나의 BCC에만 속하기 때문에 BCC를 분리할 때는 간선을 분리하는 것이 자연스럽습니다.

 

그래프를 DFS로 탐색하면서, 정점을 탐색하는 순서대로 번호를 새로 붙입시다. 이를 \(DFS\_num[v]\)라고 합시다.

또, 간선을 탐색하는 순서대로 스택에 저장합니다.

 

DFS탐색으로 만들어진 DFS 스패닝 트리에서 현재 정점 \(v\)를 루트로 하는 서브 트리에 속한 (\(v\)를 제외한) 원소의 역방향 간선으로 이동할 수 있는 모든 정점 \(u\)에 대해,

\(\min (DFS\_num[u])\)를 \(DFS\_min[v]\)라고 합시다.

 

DFS를 하던 도중, 정점 \(v\)에서 정점 \(nv\)를 탐색했을 때, \(DFS\_num[v] \le DFS\_min[nv]\)라면, 스택 내에서 \((v, nv)\)보다 나중에 삽입된 간선은 모두 하나의 BCC에 속합니다.

 

마지막으로, 이 간선들을 스택에서 모두 제거해주면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
const int SIZE = 10001;
 
int v, e;
vector <int> graph[SIZE];
 
vector<vector<pii> > BCC;
 
int DFS_cnt = 1;
int DFS_num[SIZE];
int DFS_min[SIZE];
 
vector<pii> stk;
 
void DFS(int v, int p)
{
    DFS_num[v] = DFS_min[v] = DFS_cnt++;
    for (int nv : graph[v])
    {
        if (nv == p) continue;
        if (DFS_num[v] > DFS_num[nv]) stk.push_back({ v, nv });
        // 아직 방문하지 않은 간선을 스택에 넣는다.
 
        if (DFS_num[nv])
        {
            // 역방향 간선
            DFS_min[v] = min(DFS_min[v], DFS_num[nv]);
        }
        else
        {
            // 순방향 간선
            DFS(nv, v);
            DFS_min[v] = min(DFS_min[v], DFS_min[nv]);
            if (DFS_min[nv] >= DFS_num[v])
            {
                BCC.emplace_back();
                while (true)
                {
                    pii e = stk.back(); stk.pop_back();
                    BCC.back().push_back(e);
 
                    if (e == pii(v, nv)) break;
                }
            }
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> v >> e;
    for (int i = 0; i < e; i++)
    {
        int a, b; cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
 
    for (int i = 1; i <= v; i++)
    {
        if (!DFS_num[i]) DFS(i, 0);
    }
 
    cout << BCC.size() << '\n';
    for (auto& it : BCC)
    {
        for (pii e : it) cout << "(" << e.first << "," << e.second << ") ";
        cout << "\n";
    }
}

 

---

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

11266번: 단절점

BCC를 이용해 풀 수 있는 대표적인 문제가 단절점 문제입니다.

정점을 제거 했을 때, 그래프가 2개 이상의 컴포넌트로 나누어지는 정점을 단절점이라고 합니다.

 

그래프를 BCC로 분할한 후에, 2개 이상의 BCC에 속하는 정점이 절단점이 될 것임을 쉽게 알 수 있습니다.

위의 코드를 그대로 사용한 다음 적당히 응용해서 써도 되지만, BCC 자체는 필요하지 않고 절단점만 구하고 싶다면 DFS 함수를 조금 고쳐서 더 간결하게 구현할 수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
const int SIZE = 10001;
 
int v, e;
vector <int> graph[SIZE];
 
vector<vector<pii> > BCC;
 
int DFS_cnt = 1;
int DFS_num[SIZE];
int DFS_min[SIZE];
 
bool res[SIZE];
bool isRoot[SIZE];
int child[SIZE];
 
vector<pii> stk;
 
void DFS(int v, int p)
{
    DFS_num[v] = DFS_min[v] = DFS_cnt++;
    for (int nv : graph[v])
    {
        if (nv == p) continue;
 
        if (DFS_num[nv])
        {
            DFS_min[v] = min(DFS_min[v], DFS_num[nv]);
        }
        else
        {
            child[v]++;
            DFS(nv, v);
            DFS_min[v] = min(DFS_min[v], DFS_min[nv]);
            if (DFS_min[nv] >= DFS_num[v])
            {
                // nv에서 v보다 조상으로 가는 역방향 간선이 없으므로, 단절점이다.
                res[v] = 1;
            }
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> v >> e;
    for (int i = 0; i < e; i++)
    {
        int a, b; cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
 
    for (int i = 1; i <= v; i++)
    {
        if (!DFS_num[i])
        {
            isRoot[i] = 1;
            DFS(i, 0);
        }
    }
 
    vector <int> ans;
    for (int i = 1; i <= v; i++)
    {
        if (res[i] && (!isRoot[i] || child[i] >= 2)) ans.push_back(i);
        // 예외 : 정점이 DFS 스패닝 트리의 루트라면, 자식이 2개 이상이어야 절단점이다.
    }
 
    cout << ans.size() << '\n';
    for (int i : ans) cout << i << ' ';
}

---

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

 

www.acmicpc.net/group/7712

ANZ1217