寻找图中是否存在路径

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

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

请你确定是否存在从顶点 start 开始，到顶点 end 结束的 有效路径 。

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

示例 1：

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

示例 2：

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

提示:

1 <= n <= 2 * 10⁵
0 <= edges.length <= 2 * 10⁵
edges[i].length == 2
0 <= u_i, v_i <= n - 1
u_i != v_i
0 <= start, end <= n - 1
不存在双向边
不存在指向顶点自身的边

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: bool validPath(int n, vector<vector<int>>& edges, int source, int destination) { } };

golang 解法, 执行用时: 240 ms, 内存消耗: 25.2 MB, 提交时间: 2022-12-19 11:55:24

func validPath(n int, edges [][]int, source int, destination int) bool {
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	var find func(x int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	for _, e := range edges {
		p[find(e[0])] = find(e[1])
	}
	return find(source) == find(destination)
}

cpp 解法, 执行用时: 328 ms, 内存消耗: 108.3 MB, 提交时间: 2022-12-19 11:55:13

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<int> p(n);
        iota(p.begin(), p.end(), 0);
        function<int(int)> find = [&](int x) -> int {
            if (p[x] != x) p[x] = find(p[x]);
            return p[x];
        };
        for (auto& e : edges) p[find(e[0])] = find(e[1]);
        return find(source) == find(destination);
    }
};

java 解法, 执行用时: 11 ms, 内存消耗: 95 MB, 提交时间: 2022-12-19 11:55:01

class Solution {
    private int[] p;

    public boolean validPath(int n, int[][] edges, int source, int destination) {
        p = new int[n];
        for (int i = 0; i < n; ++i) {
            p[i] = i;
        }
        for (int[] e : edges) {
            p[find(e[0])] = find(e[1]);
        }
        return find(source) == find(destination);
    }

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

python3 解法, 执行用时: 272 ms, 内存消耗: 66.8 MB, 提交时间: 2022-12-19 11:54:48

'''
并查集
判断图中两个节点是否连通，一种比较简单直接的方法是使用并查集。
先构建并查集，然后将每条边的两个节点合并。
最后查询 source 和 destination 的祖宗节点是否相同，相同则说明两个节点连通。
时间复杂度O(n+m×α(m))，空间复杂度 O(n)。其中 n 和 m 分别是节点数和边数。
'''
class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        p = list(range(n))
        for u, v in edges:
            p[find(u)] = find(v)
        return find(source) == find(destination)

golang 解法, 执行用时: 312 ms, 内存消耗: 63 MB, 提交时间: 2022-12-19 11:53:55

func validPath(n int, edges [][]int, source int, destination int) bool {
	vis := make([]bool, n)
	g := make([][]int, n)
	for _, e := range edges {
		a, b := e[0], e[1]
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	var dfs func(int) bool
	dfs = func(i int) bool {
		if i == destination {
			return true
		}
		vis[i] = true
		for _, j := range g[i] {
			if !vis[j] && dfs(j) {
				return true
			}
		}
		return false
	}
	return dfs(source)
}

cpp 解法, 执行用时: 536 ms, 内存消耗: 248.6 MB, 提交时间: 2022-12-19 11:53:42

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<bool> vis(n);
        vector<vector<int>> g(n);
        for (auto& e : edges) {
            int a = e[0], b = e[1];
            g[a].emplace_back(b);
            g[b].emplace_back(a);
        }
        function<bool(int)> dfs = [&](int i) -> bool {
            if (i == destination) return true;
            vis[i] = true;
            for (int& j : g[i]) {
                if (!vis[j] && dfs(j)) {
                    return true;
                }
            }
            return false;
        };
        return dfs(source);
    }
};

java 解法, 执行用时: 81 ms, 内存消耗: 114.7 MB, 提交时间: 2022-12-19 11:53:25

class Solution {
    private boolean[] vis;
    private List<Integer>[] g;

    public boolean validPath(int n, int[][] edges, int source, int destination) {
        vis = new boolean[n];
        g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (var e : edges) {
            int a = e[0], b = e[1];
            g[a].add(b);
            g[b].add(a);
        }
        return dfs(source, destination);
    }

    private boolean dfs(int source, int destination) {
        if (source == destination) {
            return true;
        }
        vis[source] = true;
        for (int nxt : g[source]) {
            if (!vis[nxt] && dfs(nxt, destination)) {
                return true;
            }
        }
        return false;
    }
}

python3 解法, 执行用时: 628 ms, 内存消耗: 297.5 MB, 提交时间: 2022-12-19 11:53:10

'''
我们先将 edges 转换成图 g，然后使用 DFS，判断是否存在从 source 到 destination 的路径。
过程中，用数组 vis 记录已经访问过的顶点，避免重复访问。
时间复杂度 O(n+m)，其中 n 和 m 分别是节点数和边数。
'''
class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        def dfs(i):
            if i == destination:
                return True
            vis.add(i)
            for j in g[i]:
                if j not in vis and dfs(j):
                    return True
            return False

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        vis = set()
        return dfs(source)

python3 解法, 执行用时: 608 ms, 内存消耗: 109 MB, 提交时间: 2022-07-06 14:23:39

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        neigh_dict = defaultdict(set)
        for u, v in edges:
            neigh_dict[u].add(v)
            neigh_dict[v].add(u)
        
        self.visited = set()
        def dfs(vertex):
            if vertex == destination:
                return True
            res = False
            for neigh in neigh_dict[vertex]:
                if neigh in self.visited:
                    continue
                self.visited.add(neigh)
                res = dfs(neigh) or res
                if res:
                    return res
            return res

        return dfs(source)

上一题

下一题

详情