并查集
用于解决连接问题
1 树结构并查集
初始条件下所有结点都为根节点,根节点指向自己。连接时,将一节点的根节点指向另一节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
| #include <cassert>
using namespace std;
namespace UF2{
class UnionFind{
private: int* parent; int count;
public: UnionFind(int count){ parent = new int[count]; this->count = count; for( int i = 0 ; i < count ; i ++ ) parent[i] = i; }
~UnionFind(){ delete[] parent; }
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;
parent[pRoot] = qRoot; } }; }
|
2 树结构层数优化并查集
合并时将层数较少的集合指向层数较多的集合,减少树的总层数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
| #include <cassert>
using namespace std;
namespace UF4{
class UnionFind{
private: int* rank; int* parent; 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{ parent[pRoot] = qRoot; rank[qRoot] += 1; } } }; }
|
3 路径压缩并查集
查找根节点时将父节点指向父节点的父节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
| #include <cassert>
using namespace std;
namespace UF5{
class UnionFind{
private: int* rank; int* parent; 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] ){ parent[p] = parent[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{ parent[pRoot] = qRoot; rank[qRoot] += 1; } } }; }
|
最后更新时间:
转载请注明出处