Pagini recente » Cod sursa (job #1496409) | Cod sursa (job #2714345) | Cod sursa (job #2584020) | Cod sursa (job #936899) | Cod sursa (job #1422869)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int Nmax = 100555;
int par[Nmax];
int hgt[Nmax];
int root(int a) {
if (par[a] == a)
return a;
return par[a] = root(par[a]);
}
void join(int a, int b) {
a = root(a);
b = root(b);
if (a == b)
return;
if (hgt[a] > hgt[b])
par[b] = a;
else
par[a] = b;
if (hgt[a] == hgt[b])
hgt[b]++;
}
int main()
{
ifstream f ("dfs.in");
ofstream g ("dfs.out");
int N, M, a, b;
f >> N >> M;
for (int i = 1; i <= N; i++)
par[i] = i;
while (M--) {
f >> a >> b;
join(a, b);
}
int ans = 0;
for (int i = 1; i <= N; i++)
ans += (par[i] == i);
g << ans << '\n';
return 0;
}