Pagini recente » Cod sursa (job #1114398) | Cod sursa (job #2633167) | Cod sursa (job #1926953) | Cod sursa (job #3293519) | Cod sursa (job #357332)
Cod sursa(job #357332)
//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-1,Y-1);
AddInList(Y-1,X-1);
}
for(long i = 0; i<=N-1; i++)
{
if(!viz[i])
{
Nr++;
DFS(i);
}
}
printf("%ld", 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);
}
}