Cod sursa(job #156877)

Utilizator zobicaMarin Marin zobica Data 12 martie 2008 19:39:23
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <stdio.h>

#define dim 100001

int n, m;
struct nod {
	int x;
	nod *urm;	
}; 
nod *p[dim], *S;
int viz[dim];

void adaug(nod *&p, int y){
	nod *q = new nod;
	q -> x = y;
	q -> urm = p;
	p = q;
}

void citire(){
	freopen("dfs.in", "r", stdin);
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		adaug(p[x],y);
	}
	fclose(stdin);
}

void df(int x) {
	viz[x] = 1; 
	for (nod *q = p[x]; q; q = q -> urm) 
		if (!viz[q -> x])	
			df(q -> x);		
}

void numar() {
	freopen("dfs.out", "w", stdout);	
	int nr = 0;
	for (int i = 1; i <= n ; i ++) {
		if (!viz[i]) { 
			df(i);
			nr++;
		}		
	}
	printf("%d", nr);
	fclose(stdout);
}

int main() {
	citire();
	numar();
	return 0;
}