Cod sursa(job #1445714)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 30 mai 2015 21:04:11
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <stack>
#include <vector>
#include <list>
using namespace std;
//#define _submit
#ifdef _submit
#define InFile "dfs.in"
#define OutFile "dfs.out"
#else
#define InFile "fis.in"
#define OutFile "fis.out"
#endif

class graph {
private:
	vector< list<int> > adiac;
	graph();
public:
	const list<int>& getList(int);
	graph(int);
	void addEdge(int, int);
	void DFS(int, vector<char>&);
	int size();
	int nrCompConex();
};

int graph::nrCompConex() {
	vector<char> visited(size(), 0);
	int nr = 0;
	for (int i = 0; i < size(); i++)
	if (!visited[i]) {
		nr++;
		DFS(i, visited);
	}
	return nr;
}

graph::graph(int nrnod) {
	adiac.resize(nrnod);
}

const list<int>& graph::getList(int nod) {
	return adiac[nod];
}

void graph::addEdge(int n1, int n2) {
	adiac[n1].push_back(n2);
	adiac[n2].push_back(n1);
}

int graph::size() {
	return adiac.size();
}

void graph::DFS(int startNod, vector<char> &visited) {
	stack<int> S;
	S.push(startNod);
	while (!S.empty()) {
		int curNod = S.top();
		S.pop();
		if (visited[curNod])
			continue;
		visited[curNod] = 1;
		const list<int>& vecini = getList(curNod);
		for (auto i = vecini.begin(); i != vecini.end(); ++i)
		if (!visited[*i])
			S.push(*i);
	}
}

int main() {
	assert(freopen(InFile, "r", stdin));
	assert(freopen(OutFile, "w", stdout));
	int N, M;
	scanf("%d%d", &N, &M);
	graph *G = new graph(N);
	while (M--) {
		int n1, n2;
		scanf("%d%d", &n1, &n2);
		G->addEdge(n1-1, n2-1);
	}
	printf("%d\n", G->nrCompConex());
	return 0;
}