Cod sursa(job #288042)

Utilizator dReaMerAndrei Sofian dReaMer Data 25 martie 2009 14:54:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
   #include<stdio.h>   
struct lista{
	int inf;
	lista *next;
};   
lista *v[100010];   
bool ut[100010];
   

void adauga(lista *&v,int y){   
   lista *c=new lista;   
   c->next=v;   
   c->inf=y;   
   v=c;   
}   

void dfs(int k)   {   
    ut[k]=1;   
    while(v[k])   {   
		if(!ut[v[k]->inf])   
			dfs(v[k]->inf);   
        v[k]=v[k]->next;   
   }   
}   

int main(){	
    freopen("dfs.in","r",stdin);   
    freopen("dfs.out","w",stdout);
    int n,m,i,nr=0,x,y;   
    scanf("%d%d",&n,&m);   
    for(i=1;i<=m;i++){   
		scanf("%d%d",&x,&y);   
		adauga(v[x],y);   
		adauga(v[y],x);   
    }   
    for(i=1;i<=n;i++)   
		if(!ut[i]){   
			nr++;   
			dfs(i);   
		}   
    printf("%d\n",nr); 
	return 0;
}