SCC(Strongly Connected Component)

https://jason9319.tistory.com/98

https://www.youtube.com/watch?v=H_Cg3-rv7RU&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=28

https://blog.naver.com/ndb796/221236952158

강한 연결 요소

#include <bits/stdc++.h>
 
using namespace std;
 
int id, n[1001];
bool visit[1001];
vector<int> v[1001];
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();
 
            SCC.push_back(t);
 
            visit[t] = true;
 
            if (t == start) break;
        }
 
        scc.push_back(SCC);
    }
 
    return parent;
}
 
int main(void)
{
    int vertext = 11;
 
    v[1].push_back(2);
    v[2].push_back(3);
    v[3].push_back(1);
    v[4].push_back(2);
    v[4].push_back(5);
    v[5].push_back(7);
    v[6].push_back(5);
    v[7].push_back(6);
    v[8].push_back(5);
    v[8].push_back(9);
    v[9].push_back(10);
    v[10].push_back(11);
    v[11].push_back(3);
    v[11].push_back(8);
    v[1].push_back(2);
 
    for (int i = 1; i <= vertext; i++)
        if (!visit[i]) 
            dfs(i);
    
    printf("scc의 개수 = %d\n", scc.size());
    for (int i = 0; i < scc.size(); i++)
    {
        printf("%d 번째 scc : ", i + 1);
        for (auto j : scc[i])
            printf("%d ", j);
        printf("\n");
    }
 
    return 0;
}