并查集复习
定义数组(fa[x])表示(x)的父亲
操作之前先要初始化每一个节点的父亲为自己
for(int i = 1; i <= n; i ++) fa[i] = i;
并查集基本操作:查找,合并
查找:查找元素所在集合
int query(int x)
{
while(x != fa[x]) x = fa[x];
return x;
}
路径压缩:
int query(int x)
{
while(x != fa[x]) x = fa[x] = fa[fa[x]];
return x;
}
递归版
int query(int x)
{
if(x == fa[x]) return x;
return fa[x] = query(fa[x]);
}
合并:合并两个元素所在集合
void uni(int x, int y)
{
fa[query(y)] = query(x);
}
注意要将集合所代表的元素合并
还有一种按秩合并的方法,就是把小的合并到大的里面,均摊复杂度是(log n)
几道例题
修复公路
概要:(N)个点(M)条边,每个边有一个出现的时间(t),给定点(s,t),问什么时候这两个点联通
题解:按照时间排序,每一次合并两个集合并查询点(s,t)是否在同一集合内
朋友
概要:给定两个集合(A,B)分别有(n,m)个元素,(p,q)条边(边不会联通A,B),问两个集合内和一号点联通的点的个数的最小值(这个要理解一下题意)
题解:裸的并查集,每次合并两个集合最后一个点一个点的查,注意数组的下标
带权并查集:在对并查集进行路径压缩和合并操作时,这些权值具有一定属性,即可将他们与父节点的关系,变化为与所在树的根结点关系。
食物链
这题有一种三倍并查集的做法,当然现在讲的是带权并查集(在这里是简化了,叫做种类并查集)
用0表示同类,1表示捕食,2表示被捕食,那么每次合并的时候就只需要对3取模就行了