Cod sursa(job #2045733)

Utilizator nuskyMaria Ioana nusky Data 22 octombrie 2017 19:54:12
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>

using namespace std;

class Graph{

	int vertices;
	vector<list<int> > adList;

public:
	vector<int> visited;

	Graph(int V);
	void addEdge(int x, int y);
	void DFS(int start);
};

Graph::Graph(int V){
	this->vertices = V;
	adList.resize(V + 1);
	visited.resize(V + 1, 0);
}

void Graph::addEdge(int x, int y){

	adList[x].push_back(y);
}

void Graph::DFS(int start){

	this->visited[start] = 1;
	list<int>::iterator i;

	for(i = adList[start].begin(); i != adList[start].end(); i++)
		if(this->visited[*i] == 0)
			this->DFS(*i);
}

int main(){

	int vertices, edges, x, y;
	int conex_comp = 0;

	ifstream f("dfs.in");
	f >> vertices >> edges;

	Graph my_gr(vertices);

	for(int i = 0; i < edges; i++){
		f >> x >> y;
		my_gr.addEdge(x, y);
	}
	f.close();

	for(int i = 1; i < vertices + 1; i++){
		if(my_gr.visited[i] == 0){
			conex_comp++;
			my_gr.DFS(i);
		}
	}

	ofstream g("dfs.out");
	g << conex_comp;
	g.close();
	return 0;
}