Cod sursa(job #2859567)

Utilizator cerc_info_2022Cerc Info cerc_info_2022 Data 1 martie 2022 16:11:48
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.54 kb
#include <bits/stdc++.h>

using namespace std;

vector<int>adiac[100005];
bool viz[100005];
int n,m;

void dfs(int nod) {
	if (viz[nod]==1)return;
	viz[nod]=1;
	for (auto it:adiac[nod]) {
		dfs(it);
	}
}


int main() {
	
	cin >> n >> m;
	for (int i=1; i<=m; i++) {
		int x,y;
		cin >> x >> y;
		adiac[x].push_back(y);
		adiac[y].push_back(x);
	}
	int componente_conexe=0;
	for (int i=1; i<=n; i++) {
		if (viz[i]==0) {
			dfs(i);
			componente_conexe++;
		}
	}
	
	cout << componente_conexe << '\n';
	
	
	
	return 0;
}