Cod sursa(job #1961475)

Utilizator k.bruenDan Cojocaru k.bruen Data 11 aprilie 2017 10:02:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#include <vector>
using std::vector;

std::ifstream in("dfs.in");
std::ofstream out("dfs.out");

int points, paths;

vector< vector<int> > graf;
vector<bool> visited;

void fill(int now) {
	visited[now] = true;
	for (int i = 0; i < graf[now].size(); i++) if (!visited[graf[now][i]]) fill(graf[now][i]);
}

int main() {
	in >> points >> paths;

	graf.resize(points);
	visited.resize(points, false);

	for (int i = 0; i < paths; i++) {
		int from, to;
		in >> from >> to;
		graf[from - 1].push_back(to - 1);
		graf[to - 1].push_back(from - 1);
	}

	int result = 0;

	for (int i = 0; i < points; i++) {
		if (!visited[i]) {
			fill(i);
			result++;
		}
	}

	out << result;
}