Cod sursa(job #1705009)

Utilizator laurentiu.piciuPiciu Laurentiu laurentiu.piciu Data 19 mai 2016 20:09:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>

int N, M;

using Graph = std::vector<std::vector<int> >;

Graph graph;
std::vector<bool> visited;

void count_iterative_dfs(int start) {
	std::stack<int> stiva;
	visited[start] = true;
	stiva.push(start);

	while (!stiva.empty()) {
		int curr_node = stiva.top();
		bool ok = false;
		int first_unvisited;

		for (int neigh : graph[curr_node]) {
			if (!visited[neigh]) {
				ok = true;
				first_unvisited = neigh;
				break;
			}
		}

		if (ok) {
			visited[first_unvisited] = true;
			stiva.push(first_unvisited);
		} else {
			stiva.pop();
		}
	}
}

void count_recursive_dfs(int start) {
	visited[start] = true;
	for (int neigh : graph[start]) {
		if (!visited[neigh]) {
			count_recursive_dfs(neigh);
		}
	}
}


int main() {
	std::ifstream f("dfs.in");
	std::ofstream g("dfs.out");

	f >> N >> M;

	graph.resize(N+1);
	visited.resize(N+1);

	for (int i = 0; i < M; ++i) {
		int from, to;
		f >> from >> to;
		graph[from].push_back(to);
		graph[to].push_back(from);
	}

	int components = 0;
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			components++;
			count_recursive_dfs(i);
		}
	}

	g << components;

	f.close(); g.close();

	return 0;
}