并查集 - wenzhoullq/leetcode GitHub Wiki
模板
并查集最容易弄错的就是它的根节点和它自身的节点
int[] fa ;
int find(int x){//带路径压缩的,一定要这么写
if(x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
void merge(int y,int x){
fa[find(y)] = fa[find(x)];
}
查看联通分量的方法是查看pa[index]==index,如果满足,联通分量++,反之则不动
离线并查集
给予出所有的查询,查询权重和边集排序,按查询循环,满足条件的边集在第二层循环
题目
带时间戳的并查集
1.排序
2.合并
3.对不满足要求的进行还原
Arrays.sort();//按时间戳排序
for(int i = 0 ; i < len; i++){
int left = 0 ;
while( i < len && arr[i][]==arr[left][]){//按时间隔离
i++;
}
i--;
for(int j = left ; j <= i ; j++){
if()//满足
else 还原
}
}
题目
边的并查集
题目
841. 钥匙和房间 有序图注意并查集的顺序，如果定了起点的话则需要查看fa2是不是起点了，如果是起点的话则不合并，反之则合并
1202. 交换字符串中的元素(首先注意的是,它们可以弄成一个集合，即并查集,然后用map记录并查集的根,然后用优先队列维持顺序,另一个重要点是,把所有的并查集确定后再补加入到Queue）
数组并查集
不带权
题目
带权
int[] pa;
public long[] (int[] nums, int[] removeQueries) {
int len = .length;
pa = new int[len+1];
for(int i = 0 ; i <= len ;i++ ) pa[i] = i;
long[] ans = new long[len];
long[] arr = new long[len+1];//记录并查集的权
for(int i = len -1 ;i > 0; i--){
int index = ..[i];映射
int j = find(index+1) ;//找到它右边一个的根节点
pa[index] = j;//合并，注意不要更新错了，右边一个是根节点
arr[j] += arr[index]+nums[index];//更新并查集的权
ans[i-1] =Math.max(ans[i],arr[j]);//输出想要的
}
return ans;
}
int find(int index){
if(index==pa[index]) return index;
return find(pa[index]);
}
题目
- 数组
6159. 删除操作后的最大子段和 正难则反易
- 边集
图的并查集
1.用于查询有几个联通集合
2.用于路径的查询,需要注意下图的并查询如何处理
题目
1.联通量
2.图的并查集
3.同行同列
947. 移除最多的同行或同列石头 给予的是点集，点集之间的并查集
逻辑推理并查集
根据逻辑分类成不同的并查集集合,如果发现矛盾(即在同一个并查集中
二分图
一条边上的两个点属于不同的集合，而二分图是只有两个集合，因此 （a,b）和（a,c）中，b和c必然是同一个集合
题目
886. 可能的二分法(从对立面下手，因此设定一个对立点，比如(a,b)和(a,c)对立，那么b和c必然是同一个集合（因为二分图只有两个集合），通过对立点将b和c连接