Cod sursa(job #1724461)

Utilizator andreiudilaUdila Andrei andreiudila Data 3 iulie 2016 11:55:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n,m,i,x,y;

 struct celula{
int nod;
celula *next;
};

typedef celula *lista;
lista g[100001],gt[100001],a,sol[100001];
int st[100001],vf,viz[100001];
int nrs;

void dfs(int i)
{

    viz[i]=1;
    for(lista p=g[i]; p; p=p->next)
    {
        if(viz[p->nod]==0) dfs(p->nod);

    }

    st[++vf]=i;
}

void dfs2(int i)
{
    viz[i]=1;

    for(lista p=gt[i]; p; p=p->next )
    {
        if(viz[p->nod]==0) dfs2(p->nod);
    }

    a= new celula;
    a->nod=i;
    a->next=sol[nrs];
    sol[nrs]=a;


}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y;

        a=new celula;
        a->nod=y;
        a->next=g[x];
        g[x]=a;

        a=new celula;
        a->nod=x;
        a->next=gt[y];
        gt[y]=a;

    }

    for(i=1;i<=n;++i)
    {
        if(viz[i]==0) dfs(i);
    }

    memset(viz,0,sizeof(viz));

    for(i=vf;i>=1;--i)
    {
        if(viz[st[i]]==0) ++nrs, dfs2(st[i]);
    }

    fout<<nrs<<"\n";

    for(i=1;i<=nrs;++i,fout<<"\n")
    {
        for(lista p=sol[i];p; p=p->next)
            fout<<p->nod<<" ";
    }

    return 0;
}