Cod sursa(job #3368331)

Utilizator george6115Gall George Cosmin george6115 Data 14 octombrie 2026 11:24:35
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

ifstream f("dfs.in", r);
ofstream g("dfs.out", w);
constexpr NMAX = 100000;
constexpr MMAX = 200000;
std::vector<std::vector<int>> liste_de_adiacenta;
std::bitset<NMAX> vazut;

int citire(ifstream& fisier,std::vector<std::vector<int>>& vectorul){
	int x,y;
	fisier>>x>>y
	if (x > NMAX || y>MMAX)
		return 1
	else{
	while (y){
		fisier>>x>>y;
		vectorul[x].push_back(y);
		vectorul[y].push_back(x);	
		y--;		
	}
	return 0;
	}
}

void dfs(int numar, std::vector<std::vector<int>>& vectorul, std::bitset& bitsetul){
	bitsetul.set(numar);
	for (auto x:vectorul[numar])
	{	if(bitsetul(x)==0)
			dfs(x,vectorul,bitsetul);
	}
	
}

void numaraComponenteConexe(ofstream& fisier,std::vector<std::vector<int>>& vectorul, std::bitset& bitsetul){
	int contor=0;
	for (auto x : vectorul)
		if (bitsetul(x) == 0)
		{
			contor++;
			dfs(x, vectorul, bitsetul)
		}
	fisier<<contor;
}


int main(){
	if (citire(f,liste_de_adiacenta)== 0)
		numaraComponenteConexe(g,liste_de_adiacenta,vazut);
	return 0;
}