Advertisement
roxannemafteiu

nunta- cerinta a

Feb 20th, 2017
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. ifstream fin("nunta.in");
  6. ofstream fout("nunta.out");
  7.  
  8. const int N_MAX = 2e4 + 5;
  9.  
  10. int n, m, groups;
  11. vector <int> unions[N_MAX], root, sums;
  12.  
  13. void union_2(vector <int> &a, vector <int> &b) {
  14.     vector <int> *x, *y;
  15.     if (a.size() >= b.size()) {
  16.         x = &a;
  17.         y = &b;
  18.     } else {
  19.         x = &b;
  20.         y = &a;
  21.     }
  22.  
  23.     int index = root[(*x)[0]];
  24.     for (const auto &i : (*y)) {
  25.         (*x).emplace_back(i);
  26.         root[i] = index;
  27.     }
  28.  
  29.     (*y).clear();
  30. }
  31.  
  32. int main() {
  33.     fin >> n >> m;
  34.  
  35.     root.resize(n + 1);
  36.     for (int i = 1; i <= n; ++i) {
  37.         unions[i].emplace_back(i);
  38.         root[i] = i;
  39.     }
  40.  
  41.     while (m--) {
  42.         int x, y;
  43.         fin >> x >> y;
  44.         int rx = root[x], ry = root[y];
  45.         if (rx != ry) {
  46.             union_2(unions[rx], unions[ry]);
  47.         }
  48.     }
  49.  
  50.     for (int i = 1; i <= n; ++i) {
  51.         int size_group = (int) unions[i].size();
  52.         if (size_group > 1) {
  53.             ++groups;
  54.         }
  55.     }
  56.  
  57.     fout << groups;
  58.  
  59.     fin.close();
  60.     fout.close();
  61.  
  62.     return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement