Cod sursa(job #2079972)

Utilizator ice_creamIce Cream ice_cream Data 2 decembrie 2017 10:57:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream f ("dfs.in");
ofstream g ("dfs.out");

const int NMAX = 100000;

int n;
vector <int> graf[NMAX + 1];
bool vizitat[NMAX + 1];

void citeste() {
	int m, a, b;

	f >> n >> m;
	for (int i = 1; i <= m; i++) {
		f >> a >> b;
		graf[a].push_back(b);
		graf[b].push_back(a);
	}
}

void DFS(int nod) {
	if (vizitat[nod]) return;

	vizitat[nod] = true;
	int l = graf[nod].size();
	for (int i = 0; i < l; i++)
		DFS(graf[nod][i]);
}

void rezolva() {
	int sol = 0;
	for (int i = 1; i <= n; i++)
		if (!vizitat[i]) {
			sol++;
			DFS(i);
		}
	g << sol << '\n';
}

int main() {
	citeste();
	rezolva();
	return 0;
}