Cod sursa(job #305700)

Utilizator undogSavu Victor Gabriel undog Data 18 aprilie 2009 12:41:06
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <cstdio>

struct node{
	node* next;
	int id;
};

node* v[100010];
int sel[100010];
int st[100010];

int main(){
	freopen("dfs.in","rt",stdin);
	freopen("dfs.out","wt",stdout);
	
	int m,n;
	
	scanf("%d%d",&n,&m);
	
	int i,j,l,stl;
	node* tmp;
	
	for(i=0;i<m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		
		tmp=new node;
		tmp->id=b;
		tmp->next=v[a];
		v[a]=tmp;
	}
	j=1;
	for(i=1;i<n;i++)
		if(!sel[i]){
			j++;
			st[0]=i;
			sel[i]=1;
			stl=1;
			l=0;
			while(l<stl){
				for(tmp=v[st[l]];tmp;tmp=tmp->next)
					if(!sel[tmp->id]){
						st[stl++]=tmp->id;
						sel[tmp->id]=1;
					}
				l++;
			}
		}
	
	printf("%d",j);
	
	return 0;
}