P2121 拆地毯 并查集合并

Wild_Of_The_World · 2025-02-09 11:51:02 · 个人记录

int find(int a){
    if(fa[a]!=a) return fa[a]=find(fa[a]);
    return fa[a];
}

错误合并：

u=edge[i].u,v=edge[i].v;
        if(find(u)!=find(v)){
            fa[v]=find(u);
        }

合并要祖先连祖先，如上会在两颗树合并时，只把一棵树的一个节点合过去

正确：

fa[fa[v]]=find(u);