(라이님 블로그 대회 알고리즘 따라잡기 23) 이중 연결 요소(Biconnected Component)

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220802704686&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

이중 연결 요소(Biconnected Component) (수정: 2019-02-13)

 

BCC라고도 불리는 이중 연결 요소를 공부할 예정이다.

아주 자세히 설명해준 블로그가 있어서 오늘은 라이님 블로그와 함께 아래 티스토리를 참고할 것이다.

https://ttl-blog.tistory.com/957?category=964962

[알고리즘] 그래프 (4) - 이중 연결 요소 (Biconnected Components)

 

정의)

1. 그래프 G가 biconnected하다 : G는 connected graph이며, ariticulation point를 가지고 있지 않다.

2. Biconnected component of G : G의 maximal biconnected subgraph를 의미한다.

 

→ G의 biconnected component로 G를 나눌 수 있으며 서로 다른 biconnected component는 최대 한 개의 articulation point를 공유한다.

 

성질) 

1. 같은 BCC에 속한 간선 e와 e'에 대해 아래 두 조건 중 하나를 만족해야 한다.

i) e = e' 

ii) e와 e'을 모두 포함하는 cycle이 같은 component 안에 속한다.

알고리즘

1. articulation point 찾는 알고리즘 : 아래 포스트 참고↓

https://jjo-mathstory.tistory.com/entry/Articulation-point%EB%8B%A8%EC%A0%88%EC%A0%90-%EA%B5%AC%ED%95%98%EB%8A%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

Articulation point(단절점) 구하는 알고리즘

 

2. Articulation Point를 이용해서 BCC 찾기

BCC를 찾기 위해서는 stack을 사용할 것이다.

 

정점 v에서 연결된 간선 (v, u)를 explore하면서 해당 간선을 stack에 push한다.

만약 아래와 같은 상황이라면 간선 (v, u)가 나올 때까지 stack상의 모든 간선들을 pop라며, 이것들이 하나의 BCC가 된다.

i)  v의 자식노드 u에 의해 v가 articulation point임이 밝혀짐($=low(u) \geq pre(v)$)

ii) root node v의 한 child에 대한 explor가 종료

 

코드는 gpt의 도움을 받아 짜보았다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

void BCCUtil(const vector<vector<int>>& adj, int u, vector<bool>& visited, vector<int>& disc, vector<int>& low, int& time, int parent, stack<pair<int, int>>& st) {
    int children = 0;
    visited[u] = true;
    disc[u] = low[u] = ++time;

    for (int v : adj[u]) {
        if (!visited[v]) {
            children++;
            st.push({ u, v });
            BCCUtil(adj, v, visited, disc, low, time, u, st);

            low[u] = min(low[u], low[v]);

            if ((parent != -1 && low[v] >= disc[u]) || (parent == -1 && children > 1)) {
                vector<pair<int, int>> component;
                while (st.top() != make_pair(u, v)) {
                    component.push_back(st.top());
                    st.pop();
                }
                component.push_back(st.top());
                st.pop();
                cout << "Biconnected Component: ";
                for (auto edge : component) {
                    cout << "{" << edge.first << ", " << edge.second << "} ";
                }
                cout << endl;
            }
        }
        else if (v != parent) {
            if (disc[v] < disc[u]) {
                st.push({ u, v });
            }
            low[u] = min(low[u], disc[v]);
        }
    }
}

void findBCCs(const vector<vector<int>>& adj, int V) {
    vector<int> disc(V, -1), low(V, -1);
    vector<bool> visited(V, false);
    int time = 0;
    stack<pair<int, int>> st;

    for (int u = 0; u < V; u++) {
        if (!visited[u]) {
            BCCUtil(adj, u, visited, disc, low, time, -1, st);
        }

        while (!st.empty()) {
            vector<pair<int, int>> component;
            while (!st.empty()) {
                component.push_back(st.top());
                st.pop();
            }
            cout << "Biconnected Component: ";
            for (auto edge : component) {
                cout << "{" << edge.first << ", " << edge.second << "} ";
            }
            cout << endl;
        }
    }
}

void addEdge(vector<vector<int>>& adj, int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

int main() {
    int V;

    cout << "Biconnected components in first graph\n";
    V = 5;
    vector<vector<int>> adj1(V);
    addEdge(adj1, 1, 0);
    addEdge(adj1, 0, 2);
    addEdge(adj1, 2, 1);
    addEdge(adj1, 0, 3);
    addEdge(adj1, 3, 4);
    findBCCs(adj1, V);

    cout << "\nBiconnected components in second graph\n";
    V = 4;
    vector<vector<int>> adj2(V);
    addEdge(adj2, 0, 1);
    addEdge(adj2, 1, 2);
    addEdge(adj2, 2, 3);
    findBCCs(adj2, V);

    cout << "\nBiconnected components in third graph\n";
    V = 7;
    vector<vector<int>> adj3(V);
    addEdge(adj3, 0, 1);
    addEdge(adj3, 1, 2);
    addEdge(adj3, 2, 0);
    addEdge(adj3, 1, 3);
    addEdge(adj3, 1, 4);
    addEdge(adj3, 1, 6);
    addEdge(adj3, 3, 5);
    addEdge(adj3, 4, 5);
    findBCCs(adj3, V);

    return 0;
}