Cod sursa(job #272748)

Utilizator robertzelXXX XXX robertzel Data 7 martie 2009 19:13:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <stdio.h>
#define max 100003

typedef struct nod {int inf; nod *urm;};
nod *l[max];
int n,m,i,nr, v[max];

void add (int x, int y) {
	nod *p, *q;
	
	p = new nod;
	p->inf = y;
	p->urm = l[x];
	l[x] = p;
	
	q = new nod;
	q->inf = x;
	q->urm = l[y];
	l[y] = q;
}

void backtr (int x) {
	nod *p;
	
	v[x] = 1;
	
	for (p = l[x]; p!=NULL; p = p->urm) 
	{
		if (v[p->inf] == 0)
		{
			backtr(p->inf);
		}
	}
}


void rezolva () {
		for (i=1; i<=n; i++) {
			if (v[i] == 0) {
				backtr(i);
				nr++;
			}
		}
}

void citeste () {
	int x, y;

	FILE * in  = fopen("dfs.in", "r");

	fscanf(in, "%d %d", &n, &m);

	for (i=0; i<m; i++) {
		fscanf(in, "%d %d", &x, &y);
		add(x,y);
	}


	fclose(in);
}

void scrie () {
	FILE * out = fopen("dfs.out", "w");

	fprintf(out, "%d", nr);

	fclose(out);
}

int main () {

	citeste();
	rezolva();
	scrie();

	return 0;
}