Cod sursa(job #3337830)

Utilizator livliviLivia Magureanu livlivi Data 30 ianuarie 2026 11:19:14
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100'005;

vector<int> gr[maxn];
int n, m;
bool was[maxn];

void go(int cur)
{
	if (was[cur]) return;
	was[cur] = true;
	for (auto t : gr[cur]) go(t);
}

mt19937 rng;

int main()
{
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	//~ n = 100'000;
	//~ m = 200'000;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		//~ a = rng() % n;
		//~ b = rng() % n;
		a--, b--;
		gr[a].push_back(b);
		gr[b].push_back(a);
	}
	int cnt = 0;
	auto dfs = [&](auto &&dfs, int cur) -> void {
		if (was[cur]) return;
		was[cur] = true;
		for (auto t : gr[cur]) dfs(dfs, t);
	};
	for (int i =0 ; i < n; i++) if (!was[i])
	{
		cnt++;
		go(i);
	}
	cout << cnt << endl;
	auto time = (clock() * 100) / CLOCKS_PER_SEC;
	exit(time);
}