Cod sursa(job #2819487)

Utilizator sanzianagrecuSanziana Grecu sanzianagrecu Data 18 decembrie 2021 14:25:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.57 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m, vizitat[100001];

vector <int> adia[100001];

void Dfs(int nod) {

	vizitat[nod] = 1;
	for (auto vec : adia[nod]) 
		if (!vizitat[vec])
			Dfs(vec);
}

int main() {

	fin >> n >> m;
	for (int a, b, i = 1; i <= m; ++ i) {
		fin >> a >> b;
		adia[a].push_back(b);
		adia[b].push_back(a);
	}

	int componente = 0;
	for (int i = 1; i <= n; ++ i) {
		if (!vizitat[i]) {
			componente ++;
			Dfs(i);
		}
	}

	fout << componente;

	return 0;
}