Cod sursa(job #224768)

Utilizator log2cont de teste log2 Data 30 noiembrie 2008 10:52:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <stdio.h>
#define DIM 100003

struct nod {
	long int inf;
	nod *adr;
};

nod *v[DIM],*q;
int viz[DIM];
long int n,m,i,x,y,nr;


void dfs(long int k){
	viz[k] = 1;
	nod *q = v[k];
	while (q!=NULL) {
		if (viz[q->inf] == 0) {
			dfs(q->inf);
		}
		q = q->adr;
	}
	
}


int main(){
	FILE *f = fopen("dfs.in","r");
	fscanf(f,"%d %d",&n, &m);

	for (i=1;i<=m;i++) {
		fscanf(f, "%ld %ld", &x, &y);
		q = new nod;
		q -> inf = x;
		q -> adr = v[y];
		v[y] = q;
		q = new nod;
		q -> inf = y;
		q -> adr = v[x];
		v[x] = q;
	}

	fclose(f);

	nr = 0;
	for (i = 1; i<=n;i++)
		if (viz[i] == 0) {
			nr++;
			dfs(i);
		}
	FILE *g = fopen("dfs.out", "w");
	fprintf(g, "%ld", nr);
	fclose(g);

}