Easy

题目描述

有一个具有 n 个顶点的双向图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和 vi 之间的双向边。每个顶点对由最多一条边连接，并且没有顶点存在与自身相连的边。

你想要确定是否存在从顶点 source 开始到顶点 destination 结束的有效路径。

给你数组 edges 和整数 n、source 和 destination，如果从 source 到 destination 存在有效路径，则返回 true，否则返回 false 。

示例 1：

输入：n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
输出：true
解释：存在由顶点 0 到顶点 2 的路径:
- 0 → 1 → 2 
- 0 → 2

示例 2：

输入：n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
输出：false
解释：不存在由顶点 0 到顶点 5 的路径。

提示：

  • 1 <= n <= 2 * 10^5
  • 0 <= edges.length <= 2 * 10^5
  • edges[i].length == 2
  • 0 <= ui, vi <= n - 1
  • ui != vi
  • 0 <= source, destination <= n - 1
  • 不会有重复的边
  • 不存在自环

解题思路

这是一个典型的图连通性问题，可以用多种方法解决：

方法一：并查集（推荐） 并查集是解决此类连通性问题的最佳选择。通过将所有连通的顶点归并到同一个集合中，最后只需判断源点和终点是否在同一个集合即可。时间复杂度接近线性，空间效率高。

方法二：深度优先搜索（DFS） 构建邻接表表示图，然后从源点开始进行DFS遍历。使用visited数组标记已访问的节点，如果能访问到目标节点则返回true。

方法三：广度优先搜索（BFS） 类似DFS，但使用队列进行层序遍历，同样需要visited数组防止重复访问。

考虑到题目的数据规模（最多2×10^5个节点和边），并查集在处理大规模连通性查询时效率最高，因此推荐使用并查集解法。对于小规模数据，DFS和BFS也都是不错的选择。

代码实现

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<int> parent(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        function<int(int)> find = [&](int x) -> int {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        };
        
        auto unite = [&](int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                parent[rootX] = rootY;
            }
        };
        
        for (auto& edge : edges) {
            unite(edge[0], edge[1]);
        }
        
        return find(source) == find(destination);
    }
};

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        parent = list(range(n))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def unite(x, y):
            root_x = find(x)
            root_y = find(y)
            if root_x != root_y:
                parent[root_x] = root_y
        
        for u, v in edges:
            unite(u, v)
        
        return find(source) == find(destination)

public class Solution {
    public bool ValidPath(int n, int[][] edges, int source, int destination) {
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        int Find(int x) {
            if (parent[x] != x) {
                parent[x] = Find(parent[x]);
            }
            return parent[x];
        }
        
        void Unite(int x, int y) {
            int rootX = Find(x);
            int rootY = Find(y);
            if (rootX != rootY) {
                parent[rootX] = rootY;
            }
        }
        
        foreach (int[] edge in edges) {
            Unite(edge[0], edge[1]);
        }
        
        return Find(source) == Find(destination);
    }
}

var validPath = function(n, edges, source, destination) {
    if (source === destination) return true;
    
    const graph = new Map();
    for (let i = 0; i < n; i++) {
        graph.set(i, []);
    }
    
    for (const [u, v] of edges) {
        graph.get(u).push(v);
        graph.get(v).push(u);
    }
    
    const visited = new Set();
    const queue = [source];
    visited.add(source);
    
    while (queue.length > 0) {
        const node = queue.shift();
        
        for (const neighbor of graph.get(node)) {
            if (neighbor === destination) return true;
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型并查集解法DFS/BFS解法
时间复杂度O(E × α(n))O(V + E)
空间复杂度O(n)O(V + E)

其中：

  • E 为边数，V 为顶点数，n 为顶点数
  • α(n) 为反阿克曼函数，实际应用中可视为常数
  • 并查集解法在处理多次连通性查询时效率更高

相关题目