Cod sursa(job #929810)

Utilizator VladMSBonta vlad valentin VladMS Data 27 martie 2013 11:51:54
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
//COMPONENTE TARE CONEXE
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define dim 100005
int n, m;

vector <int> g[dim], gt[dim],sol[dim];
int postviz[dim],viz[dim],nrc,ctc;

void read()
{
    int i, a, b;
    fin>>n >>m;
    for(i=1;i<=m;++i)
    {
        fin>>a >>b;
        g[a].push_back(b);
        gt[b].push_back(a);
    }
}
void df(int nod)
{
    vector <int> ::iterator it;
    viz[nod]=1;

    for(it=g[nod].begin();it!=g[nod].end();++it)
        if(viz[*it]==0)
            df(*it);

    postviz[++nrc]=nod;
}
void dft(int nod)
{
    vector <int> ::iterator it;
    viz[nod]=0;
    sol[ctc].push_back(nod);
    for(it=gt[nod].begin();it!=gt[nod].end();++it)
        if(viz[*it]==1)
            dft(*it);
}
void solve()
{
    int i;
    for(i=1;i<=n;++i)
        if(viz[i]==0)
            df(i);

    for(i=n;i>=1;--i)
        if(viz[postviz[i]]==1)
        {
            ++ctc;
            dft(postviz[i]);
        }

}
void print()
{
    vector <int> ::iterator it;
    fout<<ctc <<'\n';

    for(int i=1;i<=ctc;++i)
    {
        for(it=sol[i].begin();it!=sol[i].end();++it)
            fout<<*it <<" ";
        fout<<'\n';
    }
}
int main()
{
    read();
    solve();
    print();
    return 0;
}