Cod sursa(job #146331)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 1 martie 2008 15:56:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <cstdio>
#include <vector>

using namespace std;

const int NMAX = 1 << 17;

int N, M;
bool V[NMAX];
vector <int> G[NMAX];

void read(void) {
	FILE *fin = fopen("dfs.in", "rt");
	int i, u, v;

	fscanf(fin, " %d %d", &N, &M);

	for (i = 0; i < M; ++i) {
		fscanf(fin, " %d %d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}

	fclose(fin);
}

void DFS(int k) {
	vector <int> :: iterator i;

	V[k] = true;
	for (i = G[k].begin(); i != G[k].end(); ++i)
		if (V[*i] == false)
			DFS(*i);
}

void write(void) {
	FILE *fout = fopen("dfs.out", "wt");
	int i, cnt = 0;

	for (i = 1; i <= N; ++i)
		if (V[i] == false)
			++cnt, DFS(i);
	
	fprintf(fout, "%d\n", cnt);

	fclose(fout);
}

int main(void) {

	read();

	write();

	return 0;
}