Cod sursa(job #1458228)

Utilizator tony.hegyesAntonius Cezar Hegyes tony.hegyes Data 7 iulie 2015 10:16:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;

///// DESCRIPTION
// THIS PROGRAM EMPLOYS DEPTH-FIRST SEARCH
// ON AN INPUT OF AN UNDIRECTED GRAPH
// WITH N VERTICES AND M EDGES
// TO DETERMINE HOW MANY
// CONNECTED COMPONENTS IT HAS
/////

void dfs(int, vector<int>[], bool[]);

int main(int argc, char **argv)
{
	// INPUT
	ifstream indata("dfs.in");
	
	int n, m;
	indata >> n >> m;
	
	vector<int> edges[n + 1];
	for (int i = 0, x, y; i < m; i++) {
		indata >> x >> y;
		// there is a path from x to y
		// and from y to x
		edges[x].push_back(y);
		edges[y].push_back(x);
	}
	indata.close();
	
	// DFS
	bool visited[n + 1];
	for (int i = 1; i <= n; i++) {
		visited[i] = false;
	}
	
	int connectedComponents = 0;
	for (int i = 1; i <= n; i++) {
		if (visited[i] == true) {
			continue;
		}
		
		// if this node has not been visited
		// by doing dfs on another one already
		// then it belongs to a different
		// connected element
		connectedComponents++;
		
		// mark every node in this connected 
		// element as visited
		dfs(i, edges, visited);
	}
	
	// OUTPUT
	ofstream outdata("dfs.out");
	outdata << connectedComponents;
	outdata.close();	
	
	return 0;
}

void dfs(int currentNode, vector<int> edges[], bool visited[]) {
	// mark current node as visited
	visited[currentNode] = true;
	
	// visit all other unvisited nodes connected to the current one
	for (size_t i = 0; i < edges[currentNode].size(); i++) {
		if (visited[edges[currentNode][i]] == false) {
			dfs(edges[currentNode][i], edges, visited);
		}
	}
}