Cod sursa(job #398243)

Utilizator samuel91Asofronie Samuel samuel91 Data 18 februarie 2010 12:19:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <stdio.h> 
int n, m, viz[100005], cnt; 
typedef struct nod 
{    
int x;    
nod *a; 
} *pNod; 
pNod v[100005]; 

void add(pNod &dest, int val) 
{     
pNod p;     
p = new nod;    
p -> x = val;     
p -> a = dest;    
dest = p; 
} 
 
void citire() 
{    
freopen("dfs.in","r",stdin);     
freopen("dfs.out","w",stdout);    
scanf("%d %d",&n,&m);    
int i, x, y; 
for (i = 1; i <= m; i++)   
{        
scanf("%d %d",&x,&y);         
add(v[x], y);         
add(v[y], x); 
} 
} 

void DFS(int nod) 
{  
pNod p;    
viz[nod] = 1;    
for (p = v[nod]; p != NULL; p = p -> a) if (!viz[p -> x]) DFS(p -> x); 
}    

int main() 
{     
citire();     
int i;    
for (i = 1; i <= n; i++) if (!viz[i]) { cnt++; DFS(i);}     
printf("%d\n",cnt);     
return 0; 
}