Submission #1021497

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
using namespace std;
class DisjointSet {
public:
	vector<int> rank,p;
	DisjointSet() {}
	DisjointSet(int size) {
		rank.resize(size, 0);
		p.resize(size, 0);
		for (int i = 0; i < size; ++i) {
			makeSet(i);
		}
	}

	void makeSet(int x) {
		p[x] = x;
		rank[x] = 0;
	}

	void link(int x, int y) {
		if (rank[x] > rank[y]) {
			p[y] = x;
		}
		else {
			p[x] = y;
			if (rank[x] == rank[y]) {
				++rank[x];
			}
		}
	}

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

	void unite(int x, int y) {
		link(findSet(x), findSet(y));
	}

	int findSet(int x) {
		if (p[x] != x) {
			p[x] = findSet(p[x]);
		}
		return p[x];
	}
};

int main() {
	int n, q, com, a, b;
	cin >> n >> q;
	DisjointSet* ds = new DisjointSet(n);
	for (int i = 0; i < q; ++i) {
		cin >> com >> a >> b;
		if (com == 0) {
			ds->unite(a, b);
		}
		else {
			if (ds->same(a, b)) {
				cout << "Yes" << endl;
			}
			else {
				cout << "No" << endl;
			}
		}
	}
	return 0;
}

Submission Info

Judge Result