# Description:

## Example:

``````Note
``````

# Idea:

Union Find来找到一群里的关系网数，以及每个关系网的element个数。

# Code:

``````#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <utility>
#include <memory>
#include <cmath>

using namespace std;

class UnionFind{
public:
UnionFind(int n): id_(n), total_size_(n), num_group(n) {
for(size_t i=0; i<n; ++i){
id_[i]=i;
}
}
virtual ~UnionFind(){
}

size_t num_group;
virtual void unionCombine(int, int)=0;
virtual bool connected(int, int)=0;

virtual ostream & print(ostream & stm = cout){

for(int i=0; i<total_size_; i++){
stm<<i<<' ';
} stm<<'\n';

for(int i=0; i<total_size_; i++){
stm<<id_[i]<<' ';
} stm<<'\n';

return stm;
}

protected:
vector<int> id_;
size_t total_size_;
};

// id vector stores the group number of each node
class QuickFind: public UnionFind{
public:
QuickFind(int n): UnionFind(n){
}
void unionCombine(int p, int q) override {
if(id_[p]==id_[q]) return;

int idp = id_[p]; // Store the value, otherwise bug

for(int i=0; i<total_size_; ++i){
if(id_[i] == idp){
id_[i]=id_[q];
}
}
num_group--;
}

bool connected(int p, int q) override {
return id_[p] == id_[q];
}

};

// id vector stores the root location of each node
class QuickUnion: public UnionFind{
public:
QuickUnion(int n): UnionFind(n){
}

void unionCombine(int p, int q) override {
int rp = root_(p);
int rq = root_(q);
if(rp == rq) return;

id_[rp]=id_[rq];
num_group--;
}

bool connected(int p, int q) override {
return root_(p) == root_(q);
}

protected:
int root_(int p){
int i=p;
while( i != id_[i] ){
i = id_[i];
}

return i;
}
};

// id vector stores the root location of each node
// weight vector stores the size of the subtree at each node
class WeightedUnion: public QuickUnion{
public:
WeightedUnion(int n):QuickUnion(n), weight_(n, 1){
}

void unionCombine(int p, int q) override {
int rp = root_(p);
int rq = root_(q);
if(rp == rq) return;

// change smaller tree root to bigger tree root
// change size of bigger tree root
if(weight_[rp] < weight_[rq]){
id_[rp]=id_[rq];
weight_[rq] += weight_[rp];
}
else{
id_[rq]=id_[rp];
weight_[rp] += weight_[rq];
}

num_group--;
}

ostream & print(ostream & stm = cout) override {

for(int i=0; i<total_size_; i++){
stm<<i<<' ';
} stm<<'\n';

for(int i=0; i<total_size_; i++){
stm<<id_[i]<<' ';
} stm<<'\n';
for(int i=0; i<total_size_; i++){
stm<<weight_[i]<<' ';
} stm<<'\n';
return stm;
}

protected:
vector<int> weight_;
};

int main(){
vector<pair<int, int>> connect={{0, 1}, {0, 3}, {2, 3}, {3, 4}, {4, 5}};
int n=8;
// vector<pair<int, int>> connect={{0, 1}, {0, 3}};
// int n=4;

UnionFind * union_set1 = new QuickFind(n);
UnionFind * union_set2 = new QuickUnion(n);
UnionFind * union_set3 = new WeightedUnion(n);
UnionFind * union_set_test = union_set3;

union_set_test->print()<<'\n';
for(auto e: connect){
union_set_test->unionCombine(e.first, e.second);
// union_set1.print()<<'\n';
}
cout<<"Number of groups: "<<union_set_test->num_group<<endl;
// cout<<union_set1.connected(0, 1)<<endl;
union_set_test->print()<<'\n';

delete union_set1;
delete union_set2;
delete union_set3;
}
``````