2150번 Strongly Connected Component

https://www.acmicpc.net/problem/2150

scc(강한 연결 요소) 문제이다.

익숙해지도록 복습하고, 다시 풀어보자.

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 10001
 
int id, n[Max];
bool visit[Max];
vector<int> v[Max];
vector<vector<int> > scc;
stack<int> s;
 
int dfs(int start)
{
    n[start] = ++id;
 
    s.push(start);
 
    int parent = n[start];
 
    for (auto i : v[start])
    {
        int next = i;
 
        if (n[next] == 0) parent = min(parent, dfs(next));
        else if (!visit[next]) parent = min(parent, n[next]);
    }
 
    if (parent == n[start])
    {
        vector<int> SCC;
 
        while (1)
        {
            int t = s.top();
 
            s.pop();
 
            visit[t] = true;
 
            SCC.push_back(t);
 
            if (t == start) break;
        }
 
        sort(SCC.begin(), SCC.end());
 
        scc.push_back(SCC);
    }
 
    return parent;
}
 
int main(void)
{
    int V, E, from, to;
 
    scanf("%d %d", &V, &E);
 
    while (E--)
    {
        scanf("%d %d", &from, &to);
        v[from].push_back(to);
    }
 
    for (int i = 1; i <= V; i++)
        if (!visit[i])
            dfs(i);
 
    sort(scc.begin(), scc.end());
 
    printf("%d\n", scc.size());
    for (int i = 0; i < scc.size(); i++)
    {
        for (auto j : scc[i])
            printf("%d ", j);
        printf("-1\n");
    }
 
    return 0;
}