Cod sursa(job #270608)

Utilizator c_e_manuEmanuel Cinca c_e_manu Data 4 martie 2009 11:51:05
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include<fstream>
#define N 200000

using namespace std;

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

struct nod{
        int info;
        nod *urm;
        };
nod *prim[N],*primt[N],*sol[N];

int vizp[N],post[N],k,n,m,nr;

void insert(int where, int what)
{       nod *p;
        p=new nod;
        p->info=what;
        p->urm=prim[where];
        prim[where]=p;
}

void insertt(int where, int what)
{       nod *p;
        p=new nod;
        p->info=what;
        p->urm=primt[where];
        primt[where]=p;
}

void inserts(int where, int what)
{       nod *p;
        p=new nod;
        p->info=what;
        p->urm=sol[where];
        sol[where]=p;
}

void dfsp(int i)
{       nod *crt=prim[i];
        vizp[i]=1;
        while(crt)
        {       if(!vizp[crt->info])
                        dfsp(crt->info);
                crt=crt->urm;
        }
        post[++nr]=i;
}

void dfsm(int i)
{       nod *crt=primt[i];
        vizp[i]=0;
        inserts(k,i);
        while(crt)
        {       if(vizp[crt->info])
                        dfsm(crt->info);
                crt=crt->urm;
        }
}

int main()
{       int i,x,y;
        fin>>n>>m;
        for(i=1;i<=m;i++)
        {       fin>>x>>y;
                insert(x,y);
                insertt(y,x);
        }
        for(i=1;i<=n;i++)
        {       if(!vizp[i])
                        dfsp(i);
        }
        for(i=n;i>0;i--)
                if(vizp[post[i]])
                {       ++k;
                        dfsm(post[i]);
                }
        fout<<k<<'\n';
        nod *it;
        for(i=1;i<=k;i++)
        {       for(it=sol[i];it;it=it->urm)
                        fout<<it->info<<' ';
                fout<<'\n';
        }
        return 0;
}