寻找图中是否存在路径 图解题解

这道题到底在问什么

输入

n=3, edges=[[0,1],[1,2]], source=0, dest=2

输出

true(0-1-2 连通)

输入

n=6, edges=[[0,1],[0,2],[3,5],[5,4],[4,3]], source=0, dest=5

输出

false(分属两块)

最优解：一步一步想明白

1. 3记住「初始各自一块 → 逐边 union → 最后比 source 与 destination 的根」,下面逐帧套它。
2. 4先放下 6 个点 0~5,每个点的 parent 都指向自己,彼此独立。此刻连通块数 = 6,谁和谁都还没连上。
3. 5并查集准备就绪。接下来按给定顺序扫每条边,把边的两个端点并进同一个连通块。
4. 6第 1 条边 (0, 1):要把端点 0 和 1 连起来(两点高亮)。先各自 find 出所在块的根。
5. 7union(0, 1):把 0 那组的根接到 1 所在组的根上(永远接到对方的根,不是接到普通点),两组并成同一块(同色)。连通块数减 1,现在是 5。
6. 8第 2 条边 (0, 2):要把端点 0 和 2 连起来(两点高亮)。先各自 find 出所在块的根。
7. 9union(0, 2):把 0 那组的根接到 2 所在组的根上(永远接到对方的根,不是接到普通点),两组并成同一块(同色)。连通块数减 1,现在是 4。
8. 10第 3 条边 (3, 5):要把端点 3 和 5 连起来(两点高亮)。先各自 find 出所在块的根。
9. 11union(3, 5):把 3 那组的根接到 5 所在组的根上(永远接到对方的根,不是接到普通点),两组并成同一块(同色)。连通块数减 1,现在是 3。
10. 12第 4 条边 (5, 4):要把端点 5 和 4 连起来(两点高亮)。先各自 find 出所在块的根。
11. 13union(5, 4):把 5 那组的根接到 4 所在组的根上(永远接到对方的根,不是接到普通点),两组并成同一块(同色)。连通块数减 1,现在是 2。
12. 14第 5 条边 (4, 3):要把端点 4 和 3 连起来(两点高亮)。先各自 find 出所在块的根。
13. 15union(4, 3):find 后发现 4 和 3 已经同根了(前面的边已把它们间接连通)。这条边在块内成环,不合并新连通块、连通块数不变(仍是 2);不过 find(3) 顺手做了路径压缩,把 3 直接挂到根 4 上(parent 指针被理顺,只是不改变分块)。
14. 16五条边都并完了。看整张图:0、1、2 经边连成一块,3、4、5 经边连成另一块,共 2 个连通块。两块互不相连。
15. 17在查询前,先逐个点做一次 find 看它们各自归到哪个根,这样能一眼看清两个连通块的归属。根相同的点就是一块。
16. 18find(0) 的根是 2。这是目前见到的第 1 个不同的根,代表一个新连通块。
17. 19find(1) 的根是 2。和前面某个点的根相同,归入同一连通块。
18. 20find(2) 的根是 2。和前面某个点的根相同,归入同一连通块。
19. 21find(3) 的根是 4。这是目前见到的第 2 个不同的根,代表一个新连通块。
20. 22find(4) 的根是 4。和前面某个点的根相同,归入同一连通块。
21. 23find(5) 的根是 4。和前面某个点的根相同,归入同一连通块。
22. 24逐点 find 下来共出现 2 个不同的根:{0,1,2} 一根、{3,4,5} 另一根。两块界线清楚,接下来正式回答 source 到 destination 是否连通。
23. 25现在回答问题。先 find(source) = find(0):顺着 parent 一路找到 0 这一块的根 = 2。
24. 26再 find(destination) = find(5):找到 5 这一块的根 = 4。
25. 27比较两个根:2 和 4 不同。根不同说明 source 与 destination 分属不同连通块,彼此之间没有路径,返回 false。
26. 28反过来想:若问的是 source=0、destination=2,它俩同在上面这块、根相同,find 结果一致,就会返回 true。判定法则始终是「同根即有路径」。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        parent = list(range(n))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        for a, b in edges:
            parent[find(a)] = find(b)
        return find(source) == find(destination)

#include <functional>
#include <numeric>
#include <vector>
using namespace std;
class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<int> parent(n);
        iota(parent.begin(), parent.end(), 0);
        function<int(int)> find = [&](int x){ return parent[x] == x ? x : parent[x] = find(parent[x]); };
        for (auto &e : edges) parent[find(e[0])] = find(e[1]);
        return find(source) == find(destination);
    }
};

import java.util.*;
class Solution {
    int[] parent;
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        for (int[] e : edges) parent[find(e[0])] = find(e[1]);
        return find(source) == find(destination);
    }
    private int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
}

复杂度

面试官可能追问