Cod sursa(job #1277711)

Utilizator evodaniVasile Daniel evodani Data 28 noiembrie 2014 00:44:16
Problema Parcurgere DFS - componente conexe Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <cstdio>
#include <vector>
using namespace std;
FILE *fin, *fout;
#define NMAX 100005

bool visited[NMAX];

void dfs (int node, vector <vector<int> > &graf) {
	int ls = graf[node].size(), i, vf;
	visited[node] = 1;

	for (i=0; i<ls; ++i) {
		vf = graf[node][i];
		if (!visited[vf])
			dfs (vf, graf);
	}
}

int main() {
	fin = fopen ("dfs.in", "r");
	fout = fopen ("dfs.out", "w");

	int n, m, i, a, b, cc=0;
	fscanf (fin, "%d%d", &n, &m);
	vector <vector<int> > graf (n);
	for (i=1; i<=m; ++i) {
		fscanf (fin, "%d%d", &a, &b);
		graf[a].push_back(b);
		graf[b].push_back(a);
	}

	for (i=1; i<=n; ++i)
		if (!visited[i]) {
			dfs(i, graf);
			++cc;
		}

	fprintf (fout, "%d\n", cc);

	fclose(fin); fclose(fout);
	return 0;
}