Cod sursa(job #2959876)

Utilizator marylolloTimbus Maria marylollo Data 2 ianuarie 2023 22:18:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <vector>
using namespace std;

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

using VI  = vector<int>;
using VB  = vector<bool>;
using VVI = vector<VI>;

int n, m;
VVI G;
VB P;
int cc;

void ReadGraph();
void DF(int x);
void Solve();

int main(){
	ReadGraph();
	Solve();
	fout << cc << '\n';
	
	return 0;
}

void ReadGraph(){
	fin >> n >> m;
	G = VVI(n + 1);
	P = VB(n + 1);
	
	int x, y; 
	while(m--){
		fin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}
}

void Solve(){
	for (int node = 1; node <= n; ++node)
	     if (!P[node]){
	         DF(node);
	         cc++;
		 }
}

void DF(int x){
	P[x] = true;
	
	for (auto const & node : G[x]){
		
		if (P[node])   //   daca nodul a fost deja marcat intr-o CC
			continue;
		else
			DF(node);
	}
}