Cod sursa(job #1898215)

Utilizator TamasFlorin96Tamas Florin TamasFlorin96 Data 1 martie 2017 21:22:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <algorithm>
#include <vector>
#include <fstream>

std::vector<bool> visited;

void DFS(std::vector<std::vector<int>> &adj, int node) {
	visited[node] = true;

	for (auto x : adj[node]) {
		if (!visited[x]) {
			DFS(adj, x);
		}
	}
}

int main(void) {
	std::ifstream in("dfs.in");

	int n, m;
	in >> n >> m;
	std::vector<std::vector<int>> adj(n);

	for (int i = 0; i < m; i++) {
		int x, y;
		in >> x >> y;
		--x; --y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	in.close();

	visited = std::vector<bool>(n);

	int count = 0;
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			DFS(adj, i);
			count++;
		}
	}

	std::ofstream out("dfs.out");
	out << count<<"\n";
	out.close();

	return 0;
}