[C++] Strongly Connected Component (백준 2150번) - 강한 연결 요소

 

강한 연결 요소 - Strongly Connected Component (SCC)

방향 그래프에서 모든 정점 쌍 사이에 경로가 존재할 때, 그 그래프는 강하게 연결되어 있다고 한다.

방향 그래프에서 모든 정점 쌍 사이에 경로가 존재하는 최대 부분 그래프를 강한 연결 요소라고 한다.

 

Kosaraju 알고리즘: scc를 구하는 알고리즘

adj1: 원래 방향 그래프의 인접 리스트

adj2: 원래 그래프의 간선을 모두 반대로 뒤집은 그래프의 인접 리스트

dfs1: 원래 그래프를 dfs로 탐색함. 탐색하면서 완료 정점을 stack에 담음.

dfs2: stack의 정점들을 pop하면서 반전 그래프를 dfs로 탐색함. => dfs2 호출 횟수가 강한 연결 요소 개수

 

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

int v, e;
vector<vector<int>> adj1;
vector<vector<int>> adj2;
vector<bool> vst;
stack<int> stk;
vector<int> tmp;

void dfs1(int cur) {
    vst[cur] = true;
    for (int nxt: adj1[cur]) {
        if (!vst[nxt]) dfs1(nxt);
    }
    stk.push(cur);
}

void dfs2(int cur) {
    vst[cur] = true;
    tmp.push_back(cur);
    for (int nxt: adj2[cur]) {
        if (!vst[nxt]) dfs2(nxt);
    }
}

void solve() {
    cin >> v >> e;

    adj1 = vector<vector<int>>(v + 1);
    adj2 = vector<vector<int>>(v + 1);

    for (int i = 0; i < e; i++) {
        int a, b;
        cin >> a >> b;
        adj1[a].push_back(b);
        adj2[b].push_back(a);
    }

    vst = vector<bool>(v + 1, false);
    for (int i = 1; i < v + 1; i++) {
        if (!vst[i]) dfs1(i);
    }

    vector<vector<int>> ans;
    vst = vector<bool>(v + 1, false);
    while (!stk.empty()) {
        int x = stk.top();
        stk.pop();
        if (!vst[x]) {
            tmp = vector<int>();
            dfs2(x);
            ans.push_back(tmp);
        }
    }

    for (int i = 0; i < ans.size(); i++) {
        sort(ans[i].begin(), ans[i].end());
    }
    sort(ans.begin(), ans.end());

    cout << ans.size() << '\n';
    for (int i = 0; i < ans.size(); i++) {
        for (int x: ans[i]) cout << x << ' ';
        cout << "-1\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    for (int i = 0; i < T; i++) {
        solve();
    }
}

(AC)