Submission #3404649

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long unsigned int ll;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define REP(i,n) for(int i=0;i<n;i++)
#define REPS(i,f,n) for(int i=(f);i<(n);i++)
#define EACH(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)

#define DEBUG

#ifdef DEBUG
#define var_dump(...) fprintf(stdout, __VA_ARGS__)
#define dump(a) cout << a << "\n";
#else
#define var_dump(...) 42
#define dump(a) 42
#endif

typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy4[]={0, 0, 1, -1};
int dx4[]={1, -1, 0, 0};
int dx8[]={0, 0, 1, -1, 1, 1, -1, -1};
int dy8[]={1, -1, 0, 0, 1, -1, -1, 1};

// https://beta.atcoder.jp/contests/abc049/tasks/arc065_b

int par[200005];
int ranks[200005];

struct union_find {
    vector<int> par, ranks;

    // n要素で初期化
    void init(int n) {
        par.resize(n);
        ranks.resize(n);
        REP(i, n) {
            par[i] = i;
            ranks[i] = 0;
        }
    }

    // 木の根を求める
    int root(int x) {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = root(par[x]);
        }
    }

    // xとyの属する集合を併合
    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return;

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

    // xとyが同じ集合に属するか
    bool same(int x, int y) {
        return root(x) == root(y);
    }
};

int main() {
    int N, Q; cin >> N >> Q;
    int p, a, b;
    union_find uf;
    uf.init(N);

    REP(i, Q) {
        cin >> p >> a >> b;
        if (p == 0) {
            uf.unite(a, b);
        } else {
            cout << ((uf.same(a, b)) ? "Yes" : "No") << "\n";
        }
    }
}

Submission Info

Judge Result