Cod sursa(job #626858)

Utilizator d.andreiDiaconeasa Andrei d.andrei Data 28 octombrie 2011 14:45:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <cstdio>

#define file_in "dfs.in"
#define file_out "dfs.out"

#define nmax 101000

typedef struct nod {
	
	int val;
	nod * urm;
	
} * Qnod;

Qnod G[nmax];
int N,M,a,b,ans,i,viz[nmax];

void add(Qnod & p, int x){
	
	Qnod c=new nod;
	
	c->val=x;
	c->urm=p;
	p=c;
}

void dfs(int nod){
	
	Qnod p=G[nod] ;
	if (viz[nod])
		return ;
	
	viz[nod]=1;
	
	for (;p!=NULL;p=p->urm)
		if (!viz[p->val]) 
		    dfs(p->val);
}

int main(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &N, &M);
	while(M--){
		scanf("%d %d", &a, &b);
		
		add(G[a],b);
		add(G[b],a);
	}
	
	ans=0;
	
	for (i=1;i<=N;++i){
		if (!viz[i]){
			ans++;
			dfs(i);
		}
	}
		
	printf("%d\n", ans);

	return 0;
	
}