SHARE
TWEET

Untitled

a guest Apr 25th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <memory>
  3. #include <string>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. int get_root(int v, vector<int> &info) {
  9.     if (info[v] != v) {
  10.         return info[v] = get_root(info[v], info);
  11.     }
  12.     return v;
  13. }
  14.  
  15. void merge(int a, int b, vector<int> &info) {
  16.     int root_a = get_root(a, info);
  17.     int root_b = get_root(b, info);
  18.     if (root_a != root_b) {
  19.         info[root_b] = root_a;
  20.     }
  21. }
  22.  
  23. int main() {
  24.     int m, n;
  25.     cin >> n >> m;
  26.     vector<int> info(n + 1);
  27.     for (int i = 1; i < n + 1; i++) {
  28.         info[i] = i;
  29.     }
  30.     for (int i = 0; i != m; ++i) {
  31.         string sign;
  32.         cin >> sign;
  33.         int val1, val2;
  34.         if (sign == "b") {
  35.             cin >> val1;
  36.             cout << get_root(val1, info) << endl;
  37.         } else {
  38.             cin >> val1 >> val2;
  39.             merge(val1, val2, info);
  40.         }
  41.     }
  42. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top