Submission #420553

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <functional>
#include <cmath>

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI;
typedef pair<int,int> pii;

struct UF {
	vector<int> par, rank; //root, tree
	UF() {}
	UF(int n){ init(n); }
	void init(int n) {
		par.assign(n+4,0); rank.assign(n+4,0);
		for(int i = 0; i<n; i++) par[i] = i;
	}
	int find(int x){if(par[x] == x) return x; else return par[x] =find(par[x]);}
	void unite(int x, int y) { //unite, (add)
		x = find(x); y = find(y);
		if(x == y) return;
		if(rank[x] < rank[y]) par[x] = y;
		else{ par[y] = x; if(rank[x] == rank[y]) rank[x]++; }
	}
	bool same(int x, int y) { return find(x) == find(y); }
};


int main()
{
	
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n, q; cin >>n >>q;
	UF ufa(n);
	while(q--){
		int p,a,b;
		cin >>p >>a >>b;
		if(p==0){
			ufa.unite(a,b);
		}else{
			cout <<(ufa.same(a,b)? "Yes": "No")<<endl;
		}
	}
	return 0;
}

Submission Info

Judge Result