Pagini recente » Cod sursa (job #3363527) | Cod sursa (job #3361385) | Cod sursa (job #3361328) | Cod sursa (job #3363367) | Cod sursa (job #3362871)
#include <iostream>
using namespace std;
const int MAXN = 100000;
int sef[MAXN + 1], siz[MAXN + 1];
int nrc;
int findsef(int i) {
if (i == sef[i]) {
return i;
}
return sef[i] = findsef(sef[i]);
}
void unesc(int x, int y) {
x = findsef(x);
y = findsef(y);
if (x != y) {
nrc--;
if (siz[x] > siz[y]) {
swap(x, y);
}
sef[x] = y;
siz[y] += siz[x];
}
}
int main()
{
FILE *fin, *fout;
int n, m, i, x, y;
fin = fopen("dfs.in", "r");
fscanf(fin, "%d%d", &n, &m);
for (i = 1; i <= n; i++) {
sef[i] = i;
siz[i] = 1;
}
nrc = n;
for (i = 0; i < m; i++) {
fscanf(fin, "%d%d", &x, &y);
unesc(x, y);
}
fclose(fin);
fout = fopen("dfs.out", "w");
fprintf(fout, "%d\n", nrc);
fclose(fout);
return 0;
}