• 欢迎光临~

1971. 寻找图中是否存在路径

开发技术 开发技术 2022-12-19 次浏览

1971. 寻找图中是否存在路径

题解:并查集
并查集模板题

  1. 判断两个点是否在同一个连通块
class Solution {
    int[] p = new int[200010];

    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 并查集
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
        for (int i = 0; i < edges.length; i++) {
            int[] edge = edges[i];
            int x = find(edge[0]);
            int y = find(edge[1]);
            if (x != y) {
                p[x] = y;
            }
        }
        return find(source) == find(destination);
    }
}
``
程序员灯塔
转载请注明原文链接:1971. 寻找图中是否存在路径
喜欢 (0)