find

一句话理解

find 返回祖先，代表这个集合。

为什么要学

查询和合并都先 find。

讲解

递归找 fa[x]==x 的根。同时做路径压缩：fa[x]=find(fa[x])。

例子

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

一路向上，顺手把路径上的点直接挂到根。

常见错误

• find 写成 fa[x] 没跳到根。
• 忘记初始化 fa[i]=i。