#include <iostream>
#include <vector>
using namespace std;
class UnionFind {
private:
int m_Size;
vector<int> m_ComponnetSize;
vector<int> m_Parent;
int m_NoOfComponents;
int Find(int p) {
/*
inr root = p;
while(root != parent[root]) {
root = parent[root];
}
while(p != root) {
int next = m_Parent[p];
m_Parent[p] = root;
p = next;
}
return root;
*/
if(m_Parent[p] != p) {
m_Parent[p] = Find(m_Parent[p]);
}
return m_Parent[p];
}
public:
UnionFind(int size) {
m_NoOfComponents = size;
m_Size = m_NoOfComponents;
m_ComponnetSize = vector<int>(size);
m_Parent = vector<int>(size);
for(int i = 0; i < size; i++) {
m_Parent[i] = i;
m_ComponnetSize[i] = 1;
}
}
int Size() {
return m_Size;
}
int Components() {
return m_NoOfComponents;
}
void Union(int p, int q) {
int rootP = Find(p);
int rootQ = Find(q);
if(rootP == rootQ) return;
cout << rootP << ' ' << rootQ << endl;
if(m_ComponnetSize[rootP] < m_ComponnetSize[rootQ]) {
m_ComponnetSize[rootQ] += m_ComponnetSize[rootP];
m_Parent[p] = rootQ;
}
else {
m_ComponnetSize[rootP] += m_ComponnetSize[rootQ];
m_Parent[p] = rootP;
}
m_NoOfComponents--;
}
void PrintUF() {
for(int i = 0; i < m_Size; i++) {
cout << Find(i) << ' ';
}
cout << endl;
}
};
int main() {
UnionFind uf(5);
uf.Union(4,3);
uf.PrintUF();
uf.Union(2,1);
uf.PrintUF();
uf.Union(1,3);
uf.PrintUF();
}
CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHZlY3Rvcj4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpjbGFzcyBVbmlvbkZpbmQgewogIHByaXZhdGU6CiAgICBpbnQgbV9TaXplOwogICAgdmVjdG9yPGludD4gbV9Db21wb25uZXRTaXplOwogICAgdmVjdG9yPGludD4gbV9QYXJlbnQ7CiAgICBpbnQgbV9Ob09mQ29tcG9uZW50czsKCiAgICBpbnQgRmluZChpbnQgcCkgewogICAgICAvKgogICAgICBpbnIgcm9vdCA9IHA7CiAgICAgIHdoaWxlKHJvb3QgIT0gcGFyZW50W3Jvb3RdKSB7CiAgICAgICAgcm9vdCA9IHBhcmVudFtyb290XTsKICAgICAgfQoKICAgICAgd2hpbGUocCAhPSByb290KSB7CiAgICAgICAgaW50IG5leHQgPSBtX1BhcmVudFtwXTsKICAgICAgICBtX1BhcmVudFtwXSA9IHJvb3Q7CiAgICAgICAgcCA9IG5leHQ7CiAgICAgIH0KICAgICAgcmV0dXJuIHJvb3Q7CiAgICAgICovCiAgICAgIGlmKG1fUGFyZW50W3BdICE9IHApIHsKICAgICAgICBtX1BhcmVudFtwXSA9IEZpbmQobV9QYXJlbnRbcF0pOwogICAgICB9CgogICAgICByZXR1cm4gbV9QYXJlbnRbcF07CiAgICB9CgogIHB1YmxpYzoKICAgIFVuaW9uRmluZChpbnQgc2l6ZSkgewogICAgICBtX05vT2ZDb21wb25lbnRzID0gc2l6ZTsKICAgICAgbV9TaXplID0gbV9Ob09mQ29tcG9uZW50czsKICAgICAgbV9Db21wb25uZXRTaXplID0gdmVjdG9yPGludD4oc2l6ZSk7CiAgICAgIG1fUGFyZW50ID0gdmVjdG9yPGludD4oc2l6ZSk7CiAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCBzaXplOyBpKyspIHsKICAgICAgICBtX1BhcmVudFtpXSA9IGk7CiAgICAgICAgbV9Db21wb25uZXRTaXplW2ldID0gMTsKICAgICAgfQogICAgfQoKICAgIGludCBTaXplKCkgewogICAgICByZXR1cm4gbV9TaXplOwogICAgfSAKCiAgICBpbnQgQ29tcG9uZW50cygpIHsKICAgICAgICByZXR1cm4gbV9Ob09mQ29tcG9uZW50czsKICAgIH0KCiAgICB2b2lkIFVuaW9uKGludCBwLCBpbnQgcSkgewogICAgICBpbnQgcm9vdFAgPSBGaW5kKHApOwogICAgICBpbnQgcm9vdFEgPSBGaW5kKHEpOwogICAgICBpZihyb290UCA9PSByb290USkgcmV0dXJuOwogICAgICBjb3V0IDw8IHJvb3RQIDw8ICcgJyA8PCByb290USA8PCBlbmRsOwogICAgICBpZihtX0NvbXBvbm5ldFNpemVbcm9vdFBdIDwgbV9Db21wb25uZXRTaXplW3Jvb3RRXSkgewogICAgICAgICAgbV9Db21wb25uZXRTaXplW3Jvb3RRXSArPSBtX0NvbXBvbm5ldFNpemVbcm9vdFBdOwogICAgICAgICAgbV9QYXJlbnRbcF0gPSByb290UTsKICAgICAgfQogICAgICBlbHNlIHsKICAgICAgICAgIG1fQ29tcG9ubmV0U2l6ZVtyb290UF0gKz0gbV9Db21wb25uZXRTaXplW3Jvb3RRXTsKICAgICAgICAgIG1fUGFyZW50W3BdID0gcm9vdFA7CiAgICAgIH0KICAgICAgbV9Ob09mQ29tcG9uZW50cy0tOwogICAgfQoKICAgIHZvaWQgUHJpbnRVRigpIHsKICAgICAgZm9yKGludCBpID0gMDsgaSA8IG1fU2l6ZTsgaSsrKSB7CiAgICAgICAgY291dCA8PCBGaW5kKGkpIDw8ICcgJzsKICAgICAgfQogICAgICBjb3V0IDw8IGVuZGw7CiAgICB9Cn07CgoKaW50IG1haW4oKSB7CiAgVW5pb25GaW5kIHVmKDUpOwogIHVmLlVuaW9uKDQsMyk7CiAgdWYuUHJpbnRVRigpOwogIHVmLlVuaW9uKDIsMSk7CiAgdWYuUHJpbnRVRigpOwogIHVmLlVuaW9uKDEsMyk7CiAgdWYuUHJpbnRVRigpOwp9