Pagini recente » Cod sursa (job #646157) | Cod sursa (job #1190767) | Cod sursa (job #3278722) | Cod sursa (job #3343985) | Cod sursa (job #3337830)
#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);
}