Kosaraju's algorithm - 강한 연결 요소(SCC) 찾기

SCC(Strongly Connected Component)란?

#include <stdio.h>
#include <vector>
#include <stack>
#include <set>
#include <algorithm>
 
using namespace std;
int n, out_len;
bool check[10001], check2[10001];
vector<int> r[10001], r2[10001];
stack<int> S, S2;
set<int> out[10001];
 
void dfs(int x) {
    check[x] = true;
    for (auto it = r[x].begin(); it != r[x].end(); it++)
        if (check[*it] == false) dfs(*it);
    S.push(x);
}
 
void dfs2(int x, int w) {
    check2[x] = true;
    for (auto it = r2[x].begin(); it != r2[x].end(); it++)
        if (check2[*it] == false) dfs2(*it,w);
    out[w].insert(x);
}
 
int main() {
    int x, y, m;
 
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &x, &y);
        r[x].push_back(y), r2[y].push_back(x);
    }
 
    for (int i = 1; i <= n; i++)
        if (check[i] == false) dfs(i);
    while (!S.empty()) {
        int x = S.top();
        
        S.pop();
        if (check2[x]) continue;
 
        dfs2(x,++out_len);
    }
    sort(out + 1, out + out_len + 1);
 
    printf("%d\n", out_len);
    for (int i = 1; i <= out_len; i++) {
        for (auto it = out[i].begin(); it != out[i].end(); it++) printf("%d ", *it);
        printf("-1\n");
    }
}