[C++] 백준 2150번 - Strongly Connected Component

 강연결요소는 DFS를 두번 실행해서 연결된 요소를 찾을 수 있다. 

stack에 방문한 순서가 아닌 finished 되는 순서로 넣어야하기 때문에 이 점을 주의해서 풀면 될 것이다.

정렬을 빡세게 수행했는데 이렇게까지는 안해도 될 것 같다.

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define endl '\n'
#define vvi vector<vector<int>> 
#define vi vector<int>     
#define vb vector<bool>   

int n, m;
int follower[50001];

void first_dfs(int start, vb& visited, vvi& adj, stack<int>& st) {
    visited[start] = true;
    for (auto next : adj[start])
        if (!visited[next]) first_dfs(next, visited, adj, st);
    st.push(start);
}

void second_dfs(int start, int leader, vb& visited, vvi& adj, vi& component) {
    visited[start] = true;
    component.push_back(start);
    for (auto next : adj[start]) {
        if (!visited[next]) second_dfs(next, leader, visited, adj, component);
    }
}

vvi transpose(int vertexNum, vvi adj) {
    vvi transpose(vertexNum);
    for (int i = 1; i < vertexNum; i++) {
        for (auto next : adj[i])
            transpose[next].push_back(i);
    }
    return transpose;
}

bool comp(vi& a, vi& b) {
    if (a[0] == b[0]) return a[1] < b[1];
    return (a[0] > b[0]);
}

vvi dfs_order(int vertexNum, vvi& adj) {
    vvi temp;
    temp.resize(vertexNum);
    for (int i = 1; i < vertexNum; i++) {
        temp[i].push_back(follower[i]); temp[i].push_back(i);
    }
    sort(temp.begin() + 1, temp.end(), comp);
    return temp;
}

vvi solve(int vertexNum, vvi adj) {
    vb visited(vertexNum, false);
    stack<int> st;
    vvi tranposed = transpose(vertexNum, adj);
    for (int i = 1; i < vertexNum; i++) {
        sort(adj[i].begin(), adj[i].end());
    }
    vvi order = dfs_order(vertexNum, adj);
    for (int i = 1; i < vertexNum; i++) {
        if (!visited[order[i][1]]) first_dfs(order[i][1], visited, adj, st);
    }
    for (int i = 1; i < vertexNum; i++) visited[i] = false;

    vvi scc;
    while (!st.empty()) {
        int current = st.top(); st.pop();
        if (!visited[current]) { 
            vector<int> component; 
            second_dfs(current, current, visited, tranposed, component); 
            scc.push_back(component);
        }
    }
    return scc;
}

bool scc_cmp(vi& a, vi& b) {
    if (a[0] > b[0]) return false;
    else return true;
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    vvi v;
    v.resize(n + 1);

    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        v[a].push_back(b);
        follower[b]++;
    }
    vvi my_scc = solve(n + 1, v);

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

    cout << my_scc.size() << endl;
    for (int i = 0; i < my_scc.size(); i++) {
        for (int child : my_scc[i])
            cout << child << " ";
        cout << -1 << endl;
    }
    cout << endl;

    return 0;
}