Cod sursa(job #598898)

Utilizator nervousNervous nervous Data 27 iunie 2011 14:46:50
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <cstring>
#include <vector>

#define X1 100001

using namespace std;

ifstream in;
ofstream out;

vector <int> v[X1],w[X1],sol[X1];
int use[X1],q[X1];
int cnt;

inline void dfv(int nod)
{
    use[nod]=1;
    for(vector <int>::iterator it=v[nod].begin();it!=v[nod].end();++it)
        if(!use[*it]) dfv(*it);

    q[++q[0]]=nod;
}

inline void dfw(int nod)
{
    use[nod]=1;
    sol[cnt].push_back(nod);
    for(vector <int>::iterator it=w[nod].begin();it!=w[nod].end();++it)
        if(!use[*it]) dfw(*it);
}

int main()
{
    int M,N,x,y;

    in.open("ctc.in");
    in>>N>>M;
    for(;M;--M)
    {
        in>>x>>y;
        v[x].push_back(y);
        w[y].push_back(x);
    }
    in.close();

    memset(use,0,sizeof(use));
    memset(q,0,sizeof(q));

    for(int i=1;i<=N;++i)
        if(!use[i]) dfv(i);

    cnt=0;
    memset(use,0,sizeof(use));
    for(int i=N;i>0;--i)
        if(!use[q[i]]) ++cnt,dfw(q[i]);

    out.open("ctc.out");
    out<<cnt<<'\n';
    for(int i=1;i<=cnt;++i)
    {
        for(vector <int>::iterator it=sol[i].begin();it!=sol[i].end();++it)
            out<<*it<<' ';
        out<<'\n';
    }
    out.close();

    return 0;
}