Cod sursa(job #1991139)

Utilizator TherevengerkingSurani Adrian Therevengerking Data 15 iunie 2017 13:35:52
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define pb push_back
const int Nmax = 100000 + 5;
stack <int> S;
vector <int> v[Nmax];
vector <int> ans[Nmax];
bool viz[Nmax], inq[Nmax];
int hi[Nmax], lo[Nmax];
int n, m, cnt = -1, h;
void dfs(int nod)
{
    lo[nod] = hi[nod] = h;
    ++h;
    S.push(nod);
    inq[nod] = 1;
    viz[nod] = 1;
    for(auto i : v[nod])
        if(!viz[i])
        {
            dfs(i);
            lo[nod] = min(lo[nod],lo[i]);
        }
        else if(inq[i])lo[nod] = min(lo[nod],lo[i]);
    if(lo[nod] == hi[nod])
    {
        ++cnt;
        while(!S.empty() && S.top() != nod)
        {
            ans[cnt].pb(S.top());
            inq[S.top()] = 0;
            S.pop();
        }
        ans[cnt].pb(S.top());
        inq[S.top()] = 0;
        S.pop();
    }
}
int main()
{
    fin >> n >> m;
    for(int i = 1, x, y; i <= m; ++i)
    {
        fin >> x >> y;
        v[x].pb(y);
    }
    for(int i = 1; i <= n; ++i)viz[i] = 0;
    for(int i = 1; i <= n; ++i)
    {
        h = 1;
        if(!viz[i])dfs(i);
    }
    fout<<cnt + 1<<'\n';
    for(int i = 0; i <= cnt;++i,fout<<'\n')
        for(int j = 0; j < ans[i].size(); ++j)
            fout<<ans[i][j]<<" ";
    return 0;
}