Cod sursa(job #3318458)

Utilizator r0scatRosca Teodora Maia r0scat Data 28 octombrie 2025 12:44:41
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;

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

// parcurgerile in grafuri --> DFS si BFS
// componente tare conexe


// parcurgerea DFS
// 
// DFS(nod)
// vizitat[nod] = 1
// iteram prin toti vecinii nodului si ii marcam vizitat
// for vecin in L[nod] (lista de adiacenta)
//		if vizitat[vecin] == 0
//			DFS(vecin)
//
// pt a descoperii nr comp conexe
// for (i = 1; i <= n; i++)
//		if (vizitat[nod] == 0)
//			DFS(nod);
//			nrCompConexe++;
//



int vizitat[101];
vector<int> L[101];


void dfs(int nod) {
	vizitat[nod] = 1;
	for (int vecin : L[nod]) {
		if (vizitat[vecin] == 0)
			dfs(vecin);
	}
}

int main()
{
	int n, m, x, y, nrCompConex = 0;
	fin >> n >> m;
	for (int i = 1; i <= m; i++) {
		fin >> x >> y;
		L[x].push_back(y);
		L[y].push_back(x);
	}


	/*for (int i = 1; i <= n; i++)
	{
		cout << "nodul " << i << " are vecinii: ";
		for (int j = 0; j < L[i].size(); j++)
			cout << L[i][j] << " ";
		cout << "\n";
	}*/

	for (int i = 1; i <= n; i++)
		if (vizitat[i] == 0) {
			dfs(i);
			nrCompConex++;
		}

	fout << nrCompConex << '\n';
	return 0;
}



// BFS
// BFS(s)
// s[1] = infinit;
// s[start] = 0
// q.push(start)
// while !Q.empty()
//		nod = Q.front()
//