Cod sursa(job #168417)

Utilizator scvalexAlexandru Scvortov scvalex Data 31 martie 2008 12:42:41
Problema Parcurgere DFS - componente conexe Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int N, M;
vector<int> G[100001];
bool viz[100001];

void walk(int u) {
	viz[u] = true;
	
	for (vector<int>::iterator v = G[u].begin();
			v != G[u].end();
			++v)
		if (!viz[*v])
			walk(*v);
}

int main(int argc, char *argv[]) {
	FILE *fi = fopen("dfs.in", "r");
	fscanf(fi, "%d %d", &N, &M);
	int u, v;
	for (int i(0); i < N; ++i) {
		fscanf(fi, "%d %d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	fclose(fi);
	
	int cc(0);
	for (int i(1); i <= N; ++i)
		if (!viz[i]) {
			++cc;
			walk(i);
		}
	
	ofstream fout("dfs.out");
	fout << cc << endl;
	fout.close();
	
	return 0;
}