Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- const int maxn = 100005;
- int idx[maxn];
- int sz[maxn];
- int n;
- void init() {
- for(int i = 0; i < maxn; i++) {
- idx[i] = i;
- sz[i] = 1;
- }
- }
- int root(int x) {
- while(idx[x] != x) {
- idx[x] = idx[idx[x]];
- x = idx[x];
- }
- return x;
- }
- void join(int A, int B) {
- int root_A = root(A);
- int root_B = root(B);
- if(root_A != root_B) {
- if(sz[root_A] < sz[root_B]) {
- idx[root_A] = idx[root_B];
- sz[root_B] += sz[root_A];
- }
- else {
- idx[root_B] = idx[root_A];
- sz[root_A] += sz[root_B];
- }
- }
- }
- bool check(int A, int B) {
- return root(A) == root(B);
- }
- int main()
- {
- cin >> n;
- init();
- for(int i = 0; i < 5; i++) {
- string query;
- cin >> query;
- if(query == "join") {
- int A, B;
- cin >> A >> B;
- join(A, B);
- }
- else {
- int A, B;
- cin >> A >> B;
- cout << check(A, B) << endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement