Submission #11229037

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000;
int par[MAX_N];
int rank_of_tree[MAX_N] = {0};

void init(int n)
{

    for (int i = 0; i < n; i++)
    {
        par[i] = i;
        rank_of_tree[i] = 0;
    }
}

int find(int x)
{
    if (par[x] == x)
    {
        return x;
    }
    else
    {
        return par[x] = find(par[x]);
    }
}

void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y)
        return;

    if (rank_of_tree[x] < rank_of_tree[y])
    {
        par[x] = y;
    }
    else
    {
        par[y] = x;
        if (rank_of_tree[x] == rank_of_tree[y])
            rank_of_tree[x]++;
    }
}

bool same(int x, int y)
{
    return find(x) == find(y);
}

int main()
{
    int n, q;
    cin >> n >> q;
    init(n);
    for (int i = 0; i < q; i++)
    {
        int p, a, b;
        cin >> p >> a >> b;
        if (p == 0)
            unite(a, b);
        if (p == 1)
            cout << (same(a, b) ? "Yes" : "No") << endl;
    }
}

Submission Info

Judge Result