Cod sursa(job #1828584)

Utilizator nedelcu11Nedelcu Mihai Vlad nedelcu11 Data 13 decembrie 2016 16:42:20
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,index,m,i,s,viz[100001],pes[100001],ll[100001];
int fr;
long long nr;
stack <int> S;
vector <int> a[100001],sol[100001];
void tc(int v)
{   viz[v]=index;
    ll[v]=index;
    index++;
    S.push(v);
    pes[v]=1;
    vector<int> :: iterator it=a[v].begin(), sf=a[v].end();
    for(;it!=sf;it++)
    {   int j=(*it);
        if(!viz[j]) {tc(j);ll[v]=min(ll[v],ll[j]);}
        else if(pes[j]) ll[v]=min(ll[v],viz[j]);
    }
    if(ll[v]==viz[v])
    {   nr++;
        int w;
        do
        {   w=S.top();
            S.pop();
            pes[w]=0;
            sol[nr].push_back(w);
            if(w==1) fr++;
        }
        while(w!=v);

    }
}
void tarjan()
{   index=1;
    for(i=1;i<=n;i++)
        if(!viz[i]) {tc(i);}
}
int main()
{   f>>n>>m;
    for(i=1;i<=m;i++)
    {   int u,v;
        f>>u>>v;
        a[u].push_back(v);
    }
    tarjan();
    g<<nr<<'\n';
    for(int i=1;i<=nr;i++)
    {   vector<int> :: iterator it=sol[i].begin(),sf=sol[i].end();
        for(;it!=sf;it++)
            {g<<(*it)<<' ';}
        g<<'\n';
    }
    return 0;
}