Cod sursa(job #1451783)

Utilizator ramhackNastase Ramon ramhack Data 18 iunie 2015 15:06:31
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;


class Graph {

private:
	vector<int> *adjList;
	int connected_components;
	int size;
public:
		Graph(int size) {
			this->size = size;
			adjList = new vector<int>[size + 2];
			connected_components = 0;
		}
		~Graph() {
			delete[] adjList;
		}


		void addEdge(int u, int v) {
			adjList[u].push_back(v);
		}


		void DFS() {
			bool *visited = new bool[this->size + 2];

			for(int i = 1; i <= this->size; i++) {
				visited[i] = false;
			}
			//cout << "DFS: " ;
			for(int i = 1; i <= this->size; ++i) {

				if(visited[i] == false) {
					connected_components++;
					DFS_helper(i,visited);
				}
			}
			cout << endl << "COnexe: " << connected_components << endl;
		}


		void DFS_helper(int start_node,bool *visited) {

			vector<int>::iterator it;
			visited[start_node] = true;
			//cout << start_node << " ";

			for(it = adjList[start_node].begin(); it != adjList[start_node].end(); ++it) {

				if(visited[*it] == false) {
					DFS_helper(*it, visited);
				}
			}
		}

		int getConnectedComp() {
			return this->connected_components;
		}
};

int main(int argc, char const *argv[])
{
	
	int N, M, x, y;
	FILE *f, *out;
	out = fopen("dfs.out", "w");
	if((f = fopen("dfs.in", "r")) == NULL) {
		fprintf(stderr, "Can't open file!\n");
		return 0;
	}

	fscanf(f,"%d %d", &N, &M);
	Graph g(N);
	
	for(int i = 0; i < M; i++) {

		fscanf(f, "%d %d", &x, &y);
		
		g.addEdge(x,y);
	}
	g.DFS();
	fprintf(out, "%d\n", g.getConnectedComp());
	
	fclose(f);
	fclose(out);
	return 0;
}