Cod sursa(job #1755754)

Utilizator dropsdrop source drops Data 10 septembrie 2016 23:33:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

class Graph {
 public:
	Graph(int num_nodes) : num_nodes_(num_nodes), ctc_counter_(0) {
		edges_.resize(num_nodes_);
	}
	void AddEdge(int first_node, int second_node) {
		edges_[first_node].push_back(second_node);
		edges_[second_node].push_back(first_node);
	}
	void CalculateCtc() {
		vector<bool> visited(num_nodes_, false);
		for (int i = 0; i < num_nodes_; ++i) {
			if (!visited[i]) {
				Dfs(i, visited);
				ctc_counter_++;
			}
		}
	}
	void Dfs(int node, vector<bool> &visited) {
		visited[node] = true;
		for (int i = 0; i < edges_[node].size(); ++i) {
			int next_node = edges_[node][i];
			if (!visited[next_node]) {
				Dfs(next_node, visited);
			}
		}
	}
	int GetCtcCounter() const {
		return ctc_counter_;
	}

 private:
	vector<vector<int>> edges_;
	int num_nodes_;
	int ctc_counter_;
};

int main() {
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	int num_nodes, num_edges;
	scanf("%d %d", &num_nodes, &num_edges);
	Graph *g = new Graph(num_nodes);
	for (int i = 0; i < num_edges; ++i) {
		int first_node, second_node;
		scanf("%d %d", &first_node, &second_node);
		g->AddEdge(first_node - 1, second_node - 1);
	}
	g->CalculateCtc();
	printf("%d\n", g->GetCtcCounter());
	return 0;
}