IOIBIN - Các thùng nước
Tác giả: skyvn97
Ngôn ngữ: C++
#include<bits/stdc++.h>
#define MAX 100100
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
using namespace std;
class DisjointSet {
private:
vector<int> label; //label[x] stores the root of x if x is not root, otherwise it stores -(size of x's set).
public:
DisjointSet(){}
DisjointSet(int n) {
label.assign(n+7,-1); //label should contains at least n+1 elements, as x is 1-indexed.
//At first, each node is a seperate set of size 1.
}
int find(int x) { //find the root of set which contains x.
if (label[x]<0) return (x); //x is root iff label[x] is negative.
label[x]=find(label[x]);
return (label[x]); //find the root of x by recursion.
}
bool join(int a,int b) { // join the sets which contains a and b. Return false iff a and b are already in the same set.
int x=find(a);
int y=find(b);
if (x==y) return (false); //A set contains both a and b.
if (label[x]>label[y]) swap(x,y); //label[x]>label[y] means size(x)<size(y).
//We speed up the disjoint set by joinning the smaller set to the bigger set
label[x]+=label[y];
label[y]=x; //Update the label of x and y.
return (true);
}
int getSize(int x) { //return the size of set which contains x.
return (-label[find(x)]);
}
};
//This code is used to solve the problem: http://vn.spoj.com/problems/IOIBIN/
int main(void) {
DisjointSet dsu(MAX);
int q;
scanf("%d",&q);
REP(zz,q) {
int u,v,t;
scanf("%d%d%d",&u,&v,&t);
if (t==1) dsu.join(u,v); else printf("%d\n",dsu.find(u)==dsu.find(v));
}
return 0;
}