//// Created by liuyubobobo on 9/2/16.//#ifndef INC_04_OPTIMIZE_BY_SIZE_UNIONFIND3_H#define INC_04_OPTIMIZE_BY_SIZE_UNIONFIND3_H#include <cassert>using namespace std;namespace UF3{    class UnionFind{    private:        int* parent;        int* sz; // sz[i]表示以i为根的集合中元素个数        int count;    public:        UnionFind(int count){            parent = new int[count];            sz = new int[count];            this->count = count;            for( int i = 0 ; i < count ; i ++ ){                parent[i] = i;                sz[i] = 1;            }        }        ~UnionFind(){            delete[] parent;            delete[] sz;        }        int find(int p){            assert( p >= 0 && p < count );            while( p != parent[p] )                p = parent[p];            return p;        }        bool isConnected( int p , int q ){            return find(p) == find(q);        }        void unionElements(int p, int q){            int pRoot = find(p);            int qRoot = find(q);            if( pRoot == qRoot )                return;            if( sz[pRoot] < sz[qRoot] ){                parent[pRoot] = qRoot;                sz[qRoot] += sz[pRoot];            }            else{                parent[qRoot] = pRoot;                sz[pRoot] += sz[qRoot];            }        }    };}#endif //INC_04_OPTIMIZE_BY_SIZE_UNIONFIND3_H

//// Created by liuyubobobo on 9/2/16.//#ifndef INC_05_OPTIMIZE_BY_RANK_UNIONFIND3_H#define INC_05_OPTIMIZE_BY_RANK_UNIONFIND3_H#include <cassert>using namespace std;namespace UF3{    class UnionFind{    private:        int* parent;        int* rank; // rank[i]表示以i为根的集合所表示的树的层数        int count;    public:        UnionFind(int count){            parent = new int[count];            rank = new int[count];            this->count = count;            for( int i = 0 ; i < count ; i ++ ){                parent[i] = i;                rank[i] = 1;            }        }        ~UnionFind(){            delete[] parent;            delete[] rank;        }        int find(int p){            assert( p >= 0 && p < count );            while( p != parent[p] )                p = parent[p];            return p;        }        bool isConnected( int p , int q ){            return find(p) == find(q);        }        void unionElements(int p, int q){            int pRoot = find(p);            int qRoot = find(q);            if( pRoot == qRoot )                return;            if( rank[pRoot] < rank[qRoot] ){                parent[pRoot] = qRoot;            }            else if( rank[qRoot] < rank[pRoot]){                parent[qRoot] = pRoot;            }            else{ // rank[pRoot] == rank[qRoot]                parent[pRoot] = qRoot;                rank[qRoot] += 1;            }        }    };}#endif //INC_05_OPTIMIZE_BY_RANK_UNIONFIND3_H

//// Created by liuyubobobo on 8/31/16.//#ifndef UNIONFIND_UNIONFIND5_H#define UNIONFIND_UNIONFIND5_H#include <cassert>using namespace std;// Quick Union + rank + path compressionnamespace UF5{    class UnionFind{    private:        int* parent;        int* rank;        int count;    public:        UnionFind(int count){            parent = new int[count];            rank = new int[count];            this->count = count;            for( int i = 0 ; i < count ; i ++ ){                parent[i] = i;                rank[i] = 1;            }        }        ~UnionFind(){            delete[] parent;            delete[] rank;        }        int size(){            return count;        }        bool isConnected( int p , int q ){            return find(p) == find(q);        }        int find(int p){            assert( p >= 0 && p < count );            // path compression 1            while( p != parent[p] ){                parent[p] = parent[parent[p]];                p = parent[p];            }            return p;     最优压缩            // path compression 2//            if( p != parent[p] )//                parent[p] = find( parent[p] );//            return parent[p];        }        void unionElements(int p, int q){            int pRoot = find(p);            int qRoot = find(q);            if( pRoot == qRoot )                return;            if( rank[pRoot] < rank[qRoot] )                parent[pRoot] = qRoot;            else if( rank[qRoot] < rank[pRoot])                parent[qRoot] = pRoot;            else{ // rank[pRoot] == rank[qRoot]                parent[pRoot] = qRoot;                rank[qRoot] ++;            }        }        void show(){            for( int i = 0 ; i < count ; i ++ )                cout<<i<<" : "<<parent[i]<<endl;        }    };}#endif //UNIONFIND_UNIONFIND5_H