BOJ 2150 Strongly Connected Component

1 개요

BOJ 2150 Strongly Connected Component

• 백준 온라인 저지 2150번 문제
• BOJ 44단계

2 C++

#include <bits/stdc++.h>
using namespace std;

int V, E;
int id = 0;
int d[10001];
bool visited[10001];
vector<int> graph[10001];
vector<vector<int>> SCC;
stack<int> s;

int dfs(int x) {
    id++;
    d[x] = id;
    s.push(x);
    int parent = d[x]; 
    for(int i=0; i<graph[x].size(); i++) {
        int y = graph[x][i];
        if(d[y] == 0) {
            parent = min(parent, dfs(y));
        } else {
            if(!visited[y]) parent = min(parent, d[y]);  
        }
    }
    if(parent == d[x]) {
        vector<int> scc;
        while(true) {
            int t = s.top();
            s.pop();
            scc.push_back(t);
            visited[t] = true;
            if(t == x) break;
        }
        sort(scc.begin(), scc.end());
        SCC.push_back(scc);
    }
    return parent;
}

void solve() {
    for(int i=1; i<=V; i++) {
        if(d[i]==0) dfs(i);
    }
    cout<< SCC.size() << endl;
    sort(SCC.begin(), SCC.end(), [](vector<int> a,vector<int> b)->bool{return a[0]<b[0];});
    for(int i=0; i<SCC.size(); i++) {
        for(int j=0; j <SCC[i].size(); j++) {
            cout << SCC[i][j] << ' ';
        }
        cout << "-1\n";
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> V >> E;
    int a, b;
    for(int i=0; i<E;  i++) {
        cin >> a >> b;
        graph[a].push_back(b);
    }
    solve();
}