Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <memory>
- #include <string>
- #include <vector>
- using namespace std;
- int get_root(int v, vector<int> &info) {
- if (info[v] != v) {
- return info[v] = get_root(info[v], info);
- }
- return v;
- }
- void merge(int a, int b, vector<int> &info) {
- int root_a = get_root(a, info);
- int root_b = get_root(b, info);
- if (root_a != root_b) {
- info[root_b] = root_a;
- }
- }
- int main() {
- int m, n;
- cin >> n >> m;
- vector<int> info(n + 1);
- for (int i = 1; i < n + 1; i++) {
- info[i] = i;
- }
- for (int i = 0; i != m; ++i) {
- string sign;
- cin >> sign;
- int val1, val2;
- if (sign == "b") {
- cin >> val1;
- cout << get_root(val1, info) << endl;
- } else {
- cin >> val1 >> val2;
- merge(val1, val2, info);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement