算法训练营day56 | {0.并查集理论基础, 107.寻找存在的路径}

第11章图论-part05，当我们需判断两个元素是否在同一个集合里的时候，要想到用并查集。

0. 并查集理论基础

• 文档讲解：代码随想录
• 视频讲解：图论：并查集理论基础！
• 状态：关于并查集的模板，还有路径压缩、时空复杂度什么的看随想录。

并查集主要有两个功能：

• 将两个元素添加到一个集合中。
• 判断两个元素在不在同一个集合。

---

并查集通常用于解决连通性问题，举个例子，我们将三个元素A，B，C （分别是数字）放在同一个集合，其实就是将三个元素连通在一起，如何连通呢。只需要用一个一维数组来表示集合，即：father[A] = B，father[B] = C 这样就表述 A 与 B 与 C连通了（有向连通图）。

这里判断的条件是：只要A、B、C在同一个根下就是同一个集合。A和B的通过找根元素判断，那么对于元素C如何判断在同一个集合中？我们需要 father[C] = C，即C的根也为C，这样就方便表示 A，B，C 都在同一个集合里了。

所以father数组初始化的时候要 father[i] = i，默认自己指向自己。

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}

0.1 寻找根节点

int find(int u) {
    if (u == father[u]) return u;
    else return father[u] = find(father[u]); // 路径压缩
}

0.2 合并元素到同一个集合

void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

这里注意，u、v如果不在同一个集合中，是某个根去连通另一个根，所以代码是不冗余的。

0.3 判断两元素在不在同一个集合

bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

107. 寻找存在的路径

• 题目链接：107. 寻找存在的路径
• 文档讲解：代码随想录
• 视频讲解：图论：没想到并查集这么简单 ！| 卡码网：107. 寻找存在的路径
• 状态：模板题，巩固一下并查集的3个功能。

1.1 解题分析

第一篇写题时，合并方式写错了，并查集合并时，必须先找到根节点，再合并根。

1.2 解题小结

▶

107. 寻找存在的路径

import java.util.Scanner;

public class Main {

    static int[] father;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        father = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            father[i] = i;
        }
        while (m-- > 0) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            join(u, v);
        }
        int sour = scanner.nextInt();
        int desc = scanner.nextInt();

        System.out.println(isSame(sour, desc) ? 1 : 0);
    }

    private static int find(int u) {
        if (u == father[u]) return u;
        else {
            father[u] = find(father[u]);  // 带路径压缩
            return father[u];
        }
    }

    private static void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        father[u] = v;
    }

    private static boolean isSame(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }
}

3. 今日收获

• 坚持一下。当要判断两个节点之间的连通性，也就是解决连通性问题时，要用并查集。
• 学习时长：1.5小时