Cod sursa(job #916528)

Utilizator dudutCancel Radu Constantin dudut Data 16 martie 2013 16:52:55
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<cstdio>
#include<iostream>
using namespace std;
struct nod {
	int val;
	nod *urm;
};

void adaug( nod *&start, int x) {
	nod *p;
	p = new nod;
	if( p )
		if( start )
			if( start->urm ) {
				p->urm = start->urm;
				start->urm = p;
				p->val = x;
			}
			else {
				start->urm = p;
				p->urm = NULL;
				p->val = x;
			}
		else {
			p->val = x;
			start = p;
			start->urm = NULL;
		}		
}

void adancime( nod **v, int *viz, int i) {
	viz[i] = 1;
	nod *p = v[i];
	while(p) {
		if (viz[p->val] != 1) { adancime (v,viz,p->val); }
		p = p->urm;
	}
	
}
int main(){
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	int n,m,x,y;
	int i;
	nod **v;
	scanf("%d%d",&n,&m);
	v = (nod**) calloc (n, sizeof(nod*));
	for(i = 0; i < m; i++){
		scanf("%d%d",&x,&y);
		x--;y--;
		adaug(v[x],y);
		adaug(v[y],x);
	}
	int *viz;
	int nr = 0;
	viz = (int*) calloc( n+1, sizeof(int));
	for( i = 0;i<n;i++){
		if(viz[i]!=1) {
			nr++; adancime(v,viz,i);
		}
	}
	printf("%d",nr);
	
	return 0;
}