介绍
并查集(Union-Find)算法是一个专门针对「动态连通性」的算法,同时它也是最小生成树算法的前置知识。
模板代码
class UF{
private:
int count;
int* parent;
public:
UF(int n){
this->count = n;
this->parent = new int[n];
for(int i = 0; i<n; i++){
parent[i] = i;
}
}
void union(int p, int q){
int rootP = find(p);
int rootQ = find(q);
if(rootP == rootQ){
return;
}
parent[rootP] = rootQ;
count--;
}
//使用了路径压缩,所以不需要size数组来平衡二叉树了
int find(int x){
if(parent[x] != x){
parent[x] = find(parent[x]);
}
return parent[x];
}
bool connected(int p, int q){
return find(p) == find(q);
}
int count(void){
return count;
}
}
题目
例题1:最大人工岛
分析:
代码:
例题2:被围绕的区域
分析:
代码:
例题3:等式方程的可满足性
分析:
代码:
例题4:
分析:
代码: