Cod sursa(job #2419926)

Utilizator frodobiosif aug frodob Data 9 mai 2019 20:47:25
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
int N, M;
vector<vector<int>> graf;
vector<bool> vizitate;
int conexe = 0;
void dfs(int n);
int main() {
	fstream fin("dfs.in", ios::in);
	fstream fout("dfs.out", ios::out);
	int x, y;
	// citesc N,M
	fin >> N >> M;
	// initializare linii graf
	vector<int> a;
	graf.assign(N, a);
	// initializare vizitate
	vizitate.assign(N, false);
	// citire graf
	for (int i = 0; i < M; i++) {
		fin >> x >> y;
		(graf[x-1]).push_back(y-1);
	}

	// parcurgere dfs
	for (int i = 0; i < N; i++) {
		if (false == vizitate[i]) {
			conexe++;
			dfs(i);
		}
	}
    // afisare
	fout << conexe;
	// close
	fin.close();
	fout.close();
}
void dfs(int n) {
	vizitate[n] = true;
	vector<int>& linie = graf[n];
	for (auto& i:linie) {
		if (vizitate[i]==false) 
			dfs(i);
	}
}