Cod sursa(job #2449661)
Utilizator | Data | 20 august 2019 13:41:58 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.56 kb |
#include <cstdio>
using namespace std;
const int N = 100001;
int n, m, s;
int t[N];
int par(int a) {
if (t[a] == a)
return a;
else
return t[a] = par(t[a]);
}
int main() {
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%d %d", &n, &m);
s = n;
for (int i = 1; i <= n; i++)
t[i] = i;
for (int i = 1; i <= m; i++) {
int a, b;
scanf("%d %d", &a, &b);
a = par(a);
b = par(b);
if (a != b) {
s--;
t[a] = b;
}
}
printf("%d\n", s);
return 0;
}