Submission #3402357

---

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[100005];
int ranks[100005];

// n要素で初期化
void init(int 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;
    init(N);

    int p, a, b;
    REP(i, Q) {
        cin >> p;
        cin >> a >> b;

        if (p == 0)
            unite(a, b);
        else
            cout << (same(a, b) ? "Yes" : "No") << "\n";
    }

    return 0;
}

Submission Info

Judge Result