1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | #include <stdio.h> #include <algorithm> using namespace std; int root[200000] = { 0 }; int find(int x) { if (root[x] == x) return x; else return root[x] = find(root[x]); } void unify(int a, int b) { a = find(a); b = find(b); if (a > b) swap(a, b); root[b] = a; } int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { root[i] = i; } for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); unify(a, b); } int rst = 0; for (int i = 1; i <= n; i++) { if (root[i] == i) rst++; } printf("%d",rst); } | cs |
알고리즘/union and find