Cod sursa(job #1990707)

Utilizator fylot3Bogdan Filote fylot3 Data 13 iunie 2017 00:15:02
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <list>
#include <vector>

using namespace std;

class Graph {
	int V;
	vector<bool> visited;
	list<int> *adj;

	void recursiveDFS(int u);

public:
	Graph(int V);
	void addEdge(int u, int v);
	void depthFirstSearch(void);
};

Graph::Graph(int V) {
	this->V = V;
	adj = new list<int>[V];
}

void Graph::addEdge(int u, int v) {
	adj[u].push_back(v);
	adj[v].push_back(u);
}

void Graph::depthFirstSearch(void) {
	int nCTC = 0;

	for (int i = 1; i <= V; i++)
		visited.push_back(false);

	for (int i = 0; i < V; i++)
		if (visited.at(i) == false) {
			recursiveDFS(i);
			nCTC++;
		}

	cout << nCTC;
}

void Graph::recursiveDFS(int u) {
	visited.at(u) = true;

	list<int>::iterator i;
	for (i = adj[u].begin(); i != adj[u].end(); i++) {
		int v = *i;
		if (visited.at(v) == false)
			recursiveDFS(v);
	}
}

int main(void) {
	int N, M;
	cin >> N >> M;
	Graph g(N);
	for (int i = 1; i <= M; i++) {
		int u, v;
		cin >> u >> v;
		g.addEdge(u - 1, v - 1);
	}

	g.depthFirstSearch();
	return 0;
}