Cod sursa(job #381129)

Utilizator Dr.OptixCristian Dinu Dr.Optix Data 9 ianuarie 2010 11:19:43
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
//Problema: http://infoarena.ro/problema/dfs

#include <stdio.h>
#include <vector>

//Global data
struct TNod
{
	long Val;
	TNod *Urm;
};
TNod *vf[100001], *sf[100001];
char viz[100001];
long N, M, X, Y, Nr=0;
std::vector< std::vector<long> > Stack;
std::vector<long> Aux;

//Prototypes
void AddInList(int list, int val);
void DFS(long nod, long lvl);

int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);

    scanf("%ld%ld", &N, &M);
    for(long i = 0; i<=M-1; i++)
    {
    	scanf("%ld%ld", &X, &Y);
    	//AddInList(X-1,Y-1);
    	AddInList(Y-1,X-1);
    }

    for(long i = 0; i<=N-1; i++)
    {
        if(!viz[i])
        {
            Aux.clear();
            Aux.push_back(i+1);

            Nr++;
            DFS(i,i);
            Stack.push_back(Aux);
        }
    }

    printf("%ld\n", Nr);

    for(int i = 0; i < Nr; i++)
    {
        for(int j = 0; j < Stack[i].size(); j++)
            printf("%ld ", Stack[i][j]);
        printf("\n");
    }

	return 0;
}

void AddInList(int list, int val)
{
    if(vf[list]==NULL)
    {
        vf[list] = new TNod;
        vf[list]->Val = val;
        vf[list]->Urm = NULL;
        sf[list] = vf[list];
    }
    else
    {
        TNod *aux = new TNod;
        aux->Val =val;
        aux->Urm = NULL;
        sf[list]->Urm = aux;
        sf[list] = aux;
    }
}

void DFS(long nod,long lvl)
{
    viz[nod] = 1;
    //Aux.push_back(nod);

    for(TNod* i = vf[nod]; i!=NULL; i=i->Urm)
    {
        if(!viz[i->Val])
        {
            DFS(i->Val, lvl);
            Aux.push_back(i->Val+1);
        }
    }
}