Cod sursa(job #1490549)

Utilizator deea101Andreea deea101 Data 23 septembrie 2015 19:26:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <vector>

struct Vertex {
	std::vector <Vertex *> adj;
	bool seen;
	Vertex () : seen(false) {}
};

class Graph {
	std::vector <Vertex *> v;
	unsigned int size;
	void dfs(Vertex *);
	
public:
	Graph (unsigned int s) : v(s), size(s) {
		for(int i=0; i<v.size(); i++) v[i] = new Vertex;
	}
	unsigned int countComponents();
	void addEdge(unsigned int i, unsigned int j) {
		v[i-1]->adj.push_back(v[j-1]);
		v[j-1]->adj.push_back(v[i-1]);
	}
};

void Graph::dfs(Vertex *root) {
	unsigned int i;
	root->seen = true;
	for(i = 0; i<root->adj.size(); i++)
		if(root->adj[i]->seen == false)
			dfs(root->adj[i]);
}

unsigned int Graph::countComponents() {
	unsigned int i, c=0;
	for(i=0; i<v.size(); i++) 
		v[i]->seen = false;
	
	for(i=0; i<v.size(); i++) 
		if(v[i]->seen == false) {
			c++;
			dfs(v[i]);
		}
	return c;
}

#include <fstream>
std::ifstream f("dfs.in");
std::ofstream g("dfs.out");

int main() {
	unsigned int n,m,x,y;
	f>>n>>m;
	
	Graph G(n);
	while(m--) {
		f>>x>>y;
		G.addEdge(x,y);
	}
	
	g<<G.countComponents();
}