并查集

并查集

青春猪头少年不会在赛时被并查集少一次遍历卡165min遗憾退场

并查集，核心在查询其公共根节点，即族长

搜寻公共根节点，合并，判是否同族

//搜寻公共根节点，期间路径压缩，记录已经找到根节点的数据，省略其一步步查找的过程
int f[100000]
int find(int u){
    return f[u]==u?u:f[u]=find(f[u]);
}
void unite(int x,int y){
    f[find(x)]=find(y);
}
bool same(int x,int y){
    return find(x)==find(y)
}

核心就三点，查询，判别，合并

毒点

带圈的并查集怎么解决

os:所以这玩意为什么能卡我三个小时，道心破碎了吗（这个题其实很快就看出来思路了，但是卡在并查集了）
路径问题
问题来了，假如说我们要通过并查集判断一个有向图里面环的个数，每个环中任意节点出入度都是1，那么并查集由于其unite步骤，默认合并x的父节点到y的父节点下方，环的特殊性使得存在如下情况

1->2  2->3  3->4  4->1
f[1]=2;f[2]=3;f[3]=4;f[4]=1;
//find步骤递归将无穷进行，也就是说，我们必须规定一个环中具有某特征的数在unite时固定充当父节点

最简单的就是找大小来比较，两个根节点合并的时候，大的合并到小的或小的合并到大的
至于same中为什么写find，其实都一样，无非少一遍自家人不认自家人的unite

void unite(int x,int y){
    int tem1=find(x);
    int tem2=find(y);
	f[min(tem1,tem2)]=max(tem1,tem2);
}

f最终在跑完一整遍图之后，存的直接就是最终的父节点吗

不是！！！

f仅仅是处理过程中的路径压缩，只有在跑过去的时候才会压缩到，否则还是原根节点

举个例子，2的根节点是3，f[2]=3,之后进行了一次f[3]=f[4]的合并，f[2]依旧是3

只有在最后存完之后

for(int i=1;i<=n;i++){
    f[i]=find(i);
}

才能算是真正f[i]存的是根节点,实际前面做的都是建链，最后顺着链子跑一遍，才是真正把每个节点锚定到根节点。

满满遗憾

最后当然是遗憾离场，这个题如果不一直在并查集上考虑其实有很多简单的方法 ，行列式那题很简单，n=4，可以说是一个小模拟，但被我安排到这个题写完再写了,没关注这题，也就没注意到n小，自然以为他要写递归…赛前更是一道图题都没写，倒是关注的背包和gcd一点没考….

承队友之幸，省赛还有希望上场，加训，莫辜负。

以后再也不会盯着一个题看那么长时间了，归根到底还是做题习惯，另外就是debug的问题
不要用ai debug！ 不要用ai debug！ 不要用ai debug！赛时会很drama（重要的事情说三遍）