并查集

https://labuladong.gitee.io/algo/2/19/36/

并查集常用来解决连通性的问题，即将一个图中连通的部分划分出来。当我们判断图中两个点之间是否存在路径时，就可以用并查集解决。

能不能应用出来主要是看你抽象问题的能力，是否能够把原始问题抽象成一个有关图论的问题。

基本思路

• 用一个数组表示森林，parents【i】= j 表示节点i的父节点是j。
• 连通的节点最后都能溯源到同一个根节点。

方法
makeUnion（i，j）
find（i）
isConnected（i，j）

• 优化

private int find(int x) {
    while (parent[x] != x) {
        // 进行路径压缩
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

eg. 例题
lc 130，990