Cod sursa(job #1126472)

Utilizator jumper007Raul Butuc jumper007 Data 26 februarie 2014 23:43:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
#include <list>

using namespace std;

vector< list<int> > adj;
vector<bool> track;
int nrComp;

void readData(int &, int &);
void DepthFirstSearch(int, int);
void writeData(int);

int main(int argc, char *argv[]) {
	int nrVertices, nrEdges;

	readData(nrVertices, nrEdges);
	writeData(nrVertices);

	return 0;
}

void readData(int &nrVertices, int &nrEdges) {
	int nodeX, nodeY;
	fstream in("dfs.in", ios::in);
	in >> nrVertices >> nrEdges;
	adj.resize(nrVertices+1);
	track.resize(nrVertices+1);
	for (int i = 0; i <= nrVertices; ++i) {
		track.push_back(false);
	}
	for (int i = 0; i < nrEdges; ++i) {
		in >> nodeX >> nodeY;
		adj[nodeX].push_back(nodeY);
		adj[nodeY].push_back(nodeX);
	}
	in.close();
}

void DepthFirstSearch(int node, int nrVertices) {
	track[node] = true;
	for (list<int>::iterator it = adj[node].begin(); it != adj[node].end(); ++it) {
		if (!track[*it]) {
			DepthFirstSearch(*it, nrVertices);
		}
	}
}

void writeData(int nrVertices) {
	fstream out("dfs.out", ios::out);
	for (int i = 1; i <= nrVertices; ++i) {
		if (!track[i]) {
			nrComp++;
			DepthFirstSearch(i, nrVertices);
		}
	}
	out << nrComp++;
	out.close();
}