Silnie Spojne Skladowe

Podział grafu skierowanego na silnie spójne składowe.

#include <algorithm>
#include <vector>
#include <deque>
 
using namespace std;
 
const int NIES = 1000000000;
 
vector<vector<int> > graf;
 
int czas;
deque<int> stos;
vector<bool> na_stosie;
vector<bool> odwiedzony;
vector<int> numer;
vector<int> low;
 
void scc_dfs_visit (int s)
{
    odwiedzony[s] = true;
    numer[s] = low[s] = ++czas;
 
    stos.push_front(s);
    na_stosie[s] = true;
 
    for (vector<int>::const_iterator i = graf[s].begin() ; i != graf[s].end() ; ++i)
    {
        if (!odwiedzony[*i])
        {
            scc_dfs_visit(*i);
            low[s] = min(low[s], low[*i]);
        }
        else
        if (numer[*i] < numer[s] && na_stosie[*i] == true)
            low[s] = min(low[s], numer[*i]);
    }
 
    if (low[s] == numer[s])
    {
        int v;
 
        do
        {
            v = stos.front();
            stos.pop_front();
            na_stosie[v] = false;
 
            printf("%d\n", v);
 
        }while (v != s);
 
        printf("\n");    
    }
}
 
void scc_dfs ()
{
    czas = 0;
    stos.clear();
    na_stosie.assign(graf.size(), false);
    odwiedzony.assign(graf.size(), false);
    numer.clear(); numer.resize(graf.size());
    low.clear(); low.resize(graf.size());
 
    for (int i = 0 ; i < (int)graf.size() ; ++i)
    {
        if (!odwiedzony[i])
            scc_dfs_visit(i);
    }
}
 
void test ()
{
    int n, m, a, b;
 
    scanf("%d%d", &n, &m);
 
    graf.clear(); graf.resize(n);
 
    for (int i = 0 ; i < m ; ++i)
    {
        scanf("%d%d", &a, &b);
        graf[a].push_back(b);
    }
 
    scc_dfs();
}
 
int main ()
{
    test();
 
    return 0;
}