SCC

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

2150번: Strongly Connected Component

가 베이스이다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#define pii pair<int, int>
using namespace std;
 
vector<int> edge[10001];
 
int scc_cnt = 0;
int dfsn[10001] = { 0 };
bool finish[10001] = { false };
stack<int> s;
vector<vector<int>> ans;
int SCC(int cur)
{
    dfsn[cur] = ++scc_cnt;
    s.push(cur);
 
    int result = dfsn[cur];
    for (int i = 0; i < edge[cur].size(); i++)
    {
        int next = edge[cur][i];
 
        // 이것들이 제일 중요하다. 
        // dfsn[next]가 없으면 다음을 탐색한다. (if)
        // 싸이클이 돌면 result값을 보정한다. 대체적으로 result 값이 낮아진다. (else if)
        if (dfsn[next] == 0)
            result = min(result, SCC(next));
        else if (finish[next] == false)
            result = min(result, dfsn[next]);
 
    }
 
    //
    if (result == dfsn[cur])
    {
        vector<int> tmp;
 
        while (!s.empty())
        {
            int t = s.top();
            s.pop();
            tmp.push_back(t);
            finish[t] = true;
            if (t == cur)
                break;
        }
        sort(tmp.begin(), tmp.end());
        ans.push_back(tmp);
 
    }
    return result;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    int v, e;
    cin >> v >> e;
    int a, b;
    for (int i = 0; i < e; i++)
    {
        cin >> a >> b;
        edge[a].push_back(b);
    }
 
    //SCC(1) 이 아니다. DFS라는것을 계속 명심해야 한다.
    for (int i = 1; i <= v; i++) 
    {
        if (dfsn[i] == 0)
            SCC(i);
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
 
    for (int i = 0; i < ans.size(); i++)
    {
        for (int j = 0; j < ans[i].size(); j++)
        {
            cout << ans[i][j] << ' ';
        }
        cout << "-1\n";
    }
 
 
}