Cod sursa(job #1685200)

Utilizator RobertSSamoilescu Robert RobertS Data 11 aprilie 2016 16:00:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <string.h>

std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");


void dfs(int node, std::vector<int> *g, bool *viz) {
	
	viz[node] = true;

	for (size_t i = 0; i < g[node].size(); i++) {
		if (!viz[g[node][i]]) {
			dfs(g[node][i], g, viz);
		}
	}


}


void explore(std::vector<int> *g, bool *viz, int N) {
	
	int contor = 0;

	for (int i = 1; i <= N; i++) {
		if (!viz[i]) {
			contor++;
			dfs(i, g, viz);
		}
	}


	fout << contor << '\n';
}



int main() {

	int N, M;

	fin >> N >> M;

	//liste de adiacenta graf si graf_transpus
	std::vector<int> graph[N + 1], tgraph[N + 1];
	
	for (int i = 0; i < M; i++) {
		int x, y;
		fin >> x >> y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}

	bool viz[N + 1];
	memset(viz, false, sizeof(viz));
	explore(graph, viz, N);



	return 0;
}