Advertisement
Rockett

Untitled

May 25th, 2019
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.83 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3. #define F first
  4. #define $ ios::sync_with_stdio(0);
  5. #define S second
  6. using namespace std;
  7. using ll = long long int;
  8. using vi = vector<int>;
  9. using vii = vector<pair<int, int> >;
  10. using graph = vector<vi>;
  11. const int MAXN = 312345;
  12. const int INF = 0x3f3f3f3f;
  13. int n, pai[MAXN], r[MAXN];
  14. int findS(int i) {return i == pai[i] ? i : pai[i] = findS(pai[i]); }
  15. void join(int a, int b) {
  16.     a = findS(a);
  17.     b = findS(b);
  18.     if (a == b) return;
  19.     if (r[b] > r[a]) swap(a, b);
  20.     pai[b] = a;
  21.     r[a] += r[b];
  22.     n--;
  23. }
  24. int main() {
  25.     int m, k;
  26.     scanf("%d %d", &n, &m);
  27.     for (int i = 1; i<=n; ++i) {
  28.         pai[i] = i;
  29.         r[i] = i;
  30.     }
  31.     int u, v, w;
  32.     while (m--) {
  33.         scanf("%d %d %*d", &u, &v);
  34.         join(u, v);
  35.     }
  36.     printf("%d\n", n);
  37. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement