Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- int parent[150000];
- int my_rank[150000];
- void make_set (int v) {
- parent[v] = v;
- my_rank[v] = 0;
- }
- int find_set (int v) {
- if (v == parent[v])
- return v;
- return find_set (parent[v]);
- }
- void union_sets (int a, int b) {
- a = find_set (a);
- b = find_set (b);
- if (a != b) {
- if (my_rank[a] < my_rank[b])
- swap (a, b);
- parent[b] = a;
- if (my_rank[a] == my_rank[b])
- ++my_rank[a];
- }
- }
- int main(){
- int n, m, k;
- cin >> n >> m >> k;
- vector<int> questions[3];
- questions[0].resize(k);
- questions[1].resize(k);
- questions[2].resize(k);
- for (int i = 0; i < n; i++)
- make_set(i);
- for (int i = 0; i < m; i++){
- int a, b;
- cin >> a >> b;
- }
- for (int i = 0; i < k; i++){
- string data;
- int a, b;
- cin >> data >> a >> b;
- if (data == "ask")
- questions[0][i] = 1;
- else
- questions[0][i] = 2;
- questions[1][i] = a - 1;
- questions[2][i] = b - 1;
- }
- vector<bool> result;
- for (int i = k - 1; i >= 0; i--){
- if (questions[0][i] == 1){
- result.push_back(find_set(questions[1][i]) == find_set(questions[2][i]));
- } else
- union_sets(questions[1][i], questions[2][i]);
- }
- for (int i = result.size() - 1; i >= 0; i--) {
- if (result[i])
- cout << "YES\n";
- else
- cout << "NO\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement