Cod sursa(job #2837832)

Utilizator ItsTheFBIaaa Dani ItsTheFBI Data 22 ianuarie 2022 17:57:02
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include <iostream>
#include <vector>

const constexpr int N = 1e5+3;
int n, m;
std::vector<int> v[N];
bool vizitat[N];

/* DFS
 *
 * Marchezi nod curent ca fiind vizitat
 * Fac DFS pt toti vecinii nevizitati
 *
 */

void citire() {
	std::cin >> n >> m;

	for (auto i = 1; i <= m; i++) {
		int x, y;
		std::cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
}

void dfs(int pos) {

	vizitat[pos] = true;
	for (auto it : v[pos]) {
		if (!vizitat[it]) {
			dfs(it);
		}
	}

}

int main(int argc, char** argv) {
	citire();
	int c = 0;
	for (int i = 1; i <= n; i++) {
		if (!vizitat[i]) {
			dfs(i);
			++c;
		}
	}
	printf("Componente conexe: %i\n", c);
	return 0;
}