Cod sursa(job #1376234)

Utilizator T.C.11Tolan Cristian T.C.11 Data 5 martie 2015 16:39:59
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n,m,i,j,k,a,b,timp;
struct coce{int viz,in,out;} nod[100001];
stack<int> s[100001];
vector<int> v[100001],f[100001];

void dfs(int poz)
{
    for (vector<int>::iterator it = v[poz].begin(); it != v[poz].end(); ++it)
    {
        if (nod[*it].viz == 0)
        {
            nod[*it].viz=*it;
            timp++;
            nod[*it].in=timp;
            dfs(*it);
            timp++;
            nod[*it].out=timp;
        }
    }
}

void dfs2(int poz)
{
    for (vector<int>::iterator it = f[poz].begin(); it != f[poz].end(); ++it)
    {
        if (nod[*it].viz == 0)
        {
            nod[*it].viz=*it;
            timp++;
            s[k].push(*it);
            nod[*it].in=timp;
            dfs2(*it);
            timp++;
            nod[*it].out=timp;
        }
    }
}
bool cmp(coce a, coce b)
{
    if (a.out>b.out)
        return true;
    else
        return false;
}

int main()
{
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>a>>b;
        v[a].push_back(b);
        f[b].push_back(a);
    }
    nod[1].viz=1;
    nod[1].in=1;
    nod[1].out=2*n;
    timp=1;
    dfs(1);
    sort(nod+1,nod+1+n,cmp);
    for (i=1;i<=n;i++)
        nod[i].viz=0;
    for (i=1;i<=n;i++)
    {
        if (nod[i].viz==0)
        {
            k++;
            dfs2(i);
        }
    }
    fout<<k<<"\n";
    for (i=1;i<=k;i++)
    {
        while (s[i].empty() == false)
        {
            fout<<s[i].top()<<" ";
            s[i].pop();
        }
        fout<<"\n";
    }
    return 0;
}