Cod sursa(job #1991011)

Utilizator TherevengerkingSurani Adrian Therevengerking Data 14 iunie 2017 17:05:50
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 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];
int hi[Nmax], lo[Nmax];
int n, m, cnt = -1;
void DFS(int nod)
{
    viz[nod] = 1;
    for(auto i : v[nod])
        if(!viz[i])
        {
            hi[i] = hi[nod] + 1;
            DFS(i);
        }
}
void dfs(int nod)
{
    lo[nod] = hi[nod];
    S.push(nod);
    viz[nod] = 1;
    for(auto i : v[nod])
        if(!viz[i])
            dfs(i);
    for(auto i : v[nod])
        lo[nod] = min(lo[nod],lo[i]);
    if(lo[nod] == hi[nod])
    {
        ++cnt;
        while(!S.empty() && S.top() != nod)
        {
            ans[cnt].pb(S.top());
            S.pop();
        }
        ans[cnt].pb(S.top());
        S.pop();
    }
}
int main()
{
    fin >> n >> m;
    for(int i = 1, x, y; i <= m; ++i)
    {
        fin >> x >> y;
        v[x].pb(y);
    }
    hi[1] = 1;
    DFS(1);
    for(int i = 1; i <= n; ++i)viz[i] = 0;
    for(int i = 1; i <= n; ++i)
        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;
}