Cod sursa(job #1990767)

Utilizator fylot3Bogdan Filote fylot3 Data 13 iunie 2017 15:19:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <list>
#include <vector>
#include <fstream>

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();
};

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() {
	int nCTC = 0;
	ofstream fout("dfs.out");

	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++;
		}

	fout << 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;
	ifstream fin("dfs.in");
	fin >> N >> M;
	Graph g(N);
	for (int i = 1; i <= M; i++) {
		int u, v;
		fin >> u >> v;
		g.addEdge(u - 1, v - 1);
	}

	g.depthFirstSearch();
	return 0;
}