Cod sursa(job #543577)

Utilizator taseTanase Alexandru tase Data 28 februarie 2011 12:24:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <stdio.h>   
int n, m, viz[100005], cnt;   
typedef struct nod   
{   
    int x;   
    nod *a;   
} *pNod;   
pNod v[100005];   
void citire()   
{   
    freopen("dfs.in","r",stdin);   
    freopen("dfs.out","w",stdout);   
    scanf("%d %d",&n,&m);   
    int i, x, y;   
    pNod p;   
    for (i = 1; i <= m; i++)   
    {   
        scanf("%d %d",&x,&y);   
        p = new nod;   
        p -> x = x;   
        p -> a = v[y];   
        v[y] = p;   
        p = new nod;   
        p -> x = y;   
        p -> a = v[x];   
        v[x] = p;   
    }   
}   
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;   
}