Cod sursa(job #543590)

Utilizator liv182copoiu liviu liv182 Data 28 februarie 2011 12:34:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <stdio.h>   
int n, m, viz[100005], nr;   
typedef struct nod   
{   
    int x;   
    nod *b;   
} *pNod;   
pNod v[100005];   
void citire()   
{   
    freopen("dfs.in","r",stdin);   
    freopen("dfs.out","w",stdout);   
    scanf("%d %d",&n,&m);   
    int x, y;   
    pNod a;   
    for (int i=1;i<=m;i++)   
    {   
        scanf("%d%d",&x,&y);   
        a=new nod;   
        a->x=x;   
		a->b=v[y];   
        v[y]=a;   
        a=new nod;   
        a->x=y;   
        a->b=v[x];   
        v[x]=a;   
    }   
}   
void DFS(int nod)   
{   
    pNod a;   
    viz[nod]=1;   
    for (a=v[nod];a!=NULL;a=a->b) 
		if (!viz[a->x])DFS(a->x);   
}      
  
int main()   
{   
    citire();    
    for (int i =1;i<=n;i++)
		if (!viz[i]) 
		{ 
			nr++;
			DFS(i);
		}   
    printf("%d\n",nr
	);   
    return 0;   

}