Cod sursa(job #803267)

Utilizator gramatovici_paulGramatovici Paul gramatovici_paul Data 27 octombrie 2012 12:12:33
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");

vector <int> lista[111111],listab[111111],a[111111];
bool marcat1[111111],marcat2[111111];
int t[111111],nr,k;

void dfs1(int poz)
{
    int i;
    for(i=0;i<lista[poz].size();++i)
    {
        if(!marcat1[lista[poz][i]])
        {
            marcat1[lista[poz][i]]=true;
            dfs1(lista[poz][i]);
        }
    }
    t[++nr]=poz;
}

void dfs2(int poz)
{
    int i;
    a[k].push_back(poz);
    for(i=0;i<listab[poz].size();++i)
    {
        if(!marcat2[listab[poz][i]])
        {
            marcat2[listab[poz][i]]=true;
            dfs2(listab[poz][i]);
        }
    }
}


int main()
{
    int i,j,n,m,p,q;
    in>>n>>m;
    for(i=1;i<=m;++i)
    {
        in>>p>>q;
        lista[p].push_back(q);
        listab[q].push_back(p);
    }
    for(i=1;i<=n;++i)
    {
        if(!marcat1[i])
        {
            marcat1[i]=true;
            dfs1(i);
        }
    }
    for(i=n;i;--i)
    {
        if(!marcat2[t[i]])
        {
            marcat2[t[i]]=true;
            ++k;
            dfs2(t[i]);
        }
    }
    out<<k<<"\n";
    for(i=1;i<=k;++i)
    {
        for(j=0;j<a[i].size();++j)
            out<<a[i][j]<<" ";
        out<<"\n";
    }
    return 0;
}