[c++] 강한 연결 요소 찾기 알고리즘

08 Dec 2023

강한 연결 요소(Strongly Connected Components, SCC)는 그래프 이론에서 중요한 개념 중 하나입니다. 그래프 내에서 SCC를 찾는 것은 매우 유용하며, 이를 활용하여 다양한 문제들을 해결할 수 있습니다. 이번 글에서는 강한 연결 요소를 찾는 알고리즘을 살펴보겠습니다.

강한 연결 요소란 무엇인가요?

강한 연결 요소는 방향 그래프에서의 연결이 강한 부분을 의미합니다. 즉, 한 SCC에 속한 임의의 두 정점 u와 v에 대해 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재해야 합니다.

코사라주 알고리즘

코사라주 알고리즘은 강한 연결 요소를 찾는 데 사용되는 대표적인 알고리즘 중 하나입니다. 이 알고리즘은 다음과 같은 단계로 수행됩니다.

주어진 그래프에 대해 DFS(Depth-First Search)를 수행하여 각 정점에 탐색 순서를 기록합니다.
주어진 그래프의 간선 방향을 뒤집어 역방향 그래프를 생성합니다.
역방향 그래프에 대해 다시 DFS를 수행하되, 탐색 순서의 역순으로 탐색합니다.
위 과정을 통해 찾은 강한 연결 요소들이 SCC입니다.

예시 코드

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

using namespace std;

vector<vector<int>> graph, reverseGraph;
vector<bool> visited;
stack<int> s;

void dfs(int v) {
    visited[v] = true;
    for (int next : graph[v]) {
        if (!visited[next]) {
            dfs(next);
        }
    }
    s.push(v);
}

void reverseDfs(int v, vector<int>& scc) {
    visited[v] = true;
    scc.push_back(v);
    for (int next : reverseGraph[v]) {
        if (!visited[next]) {
            reverseDfs(next, scc);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    graph.resize(n + 1);
    reverseGraph.resize(n + 1);
    visited.assign(n + 1, false);

    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        reverseGraph[b].push_back(a);
    }

    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            dfs(i);
        }
    }

    visited.assign(n + 1, false);
    vector<vector<int>> scc;
    while (!s.empty()) {
        int v = s.top();
        s.pop();
        if (!visited[v]) {
            vector<int> curScc;
            reverseDfs(v, curScc);
            scc.push_back(curScc);
        }
    }

    for (auto& component : scc) {
        sort(component.begin(), component.end());
        for (int v : component) {
            cout << v << " ";
        }
        cout << "\n";
    }

    return 0;
}

위의 예시 코드는 코사라주 알고리즘을 사용하여 강한 연결 요소를 찾는 코드입니다.

마치며

강한 연결 요소는 다양한 분야에서 활용되며, 그래프 이론에서 중요한 개념 중 하나입니다. 코사라주 알고리즘을 통해 강한 연결 요소를 효과적으로 찾을 수 있으며, 이를 응용하여 실제 문제를 해결하는 데 활용할 수 있습니다.

참고 문헌

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.