警钟撅烂——并查集

· · 个人记录

并查集的易错点

时间复杂度

见P1197 [JSOI2008] 星球大战 （题目思路见 题解 或 提交记录 ）

易错点：
并查集的查找根节点

inline int find(int x){
    if(dsu[x] == x) return x;
    return find(dsu[x]);
}

仔细想想好像并没有什么不合适
但是可以优化！

inline int find(int x){
    if(dsu[x] == x) return x;
    return dsu[x] = find(dsu[x]);
}

看出区别来了：
如果用上面的方法，每次查找要花的时间是这个节点的深度
但是优化了之后，一次查找要花的时间还是它的深度
每查找一次之后，将节点直接连接成根，节点的深度变为1，就会变成类似菊花图的并查集，再查找时仅需花O（1）的复杂度！

看上去没少多少，但是如果不优化，就会有两个点T！点击查看
废了我两个小时 将警钟撅烂！！