Cod sursa(job #357330)

Utilizator Dr.OptixCristian Dinu Dr.Optix Data 18 octombrie 2009 20:54:26
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
//Problema: http://infoarena.ro/problema/dfs

#include <stdio.h>

//Global data
struct TNod
{
	long Val;
	TNod *Urm;
};
TNod *vf[100001], *sf[100001];
char viz[100001];
long N, M, X, Y, Nr=0;

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

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

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

    for(long i = 0; i<=N-1; i++)
    {
        if(!viz[i])
        {
            Nr++;
            DFS(i);
        }
    }

    printf("%lld", Nr);

	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)
{
    viz[nod] = 1;
    for(TNod* i = vf[nod]; i!=NULL; i=i->Urm)
    {
        if(!viz[i->Val])
            DFS(i->Val);
    }
}