Question

1971. Find if Path Exists in Graph

中文文档

Description

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex source to vertex destination.

Given edges and the integers n, source, and destination, return true_ if there is a valid path from _source_ to _destination_, or _false_ otherwise__._

 

Example 1:

Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:
- 0 → 1 → 2
- 0 → 2

Example 2:

Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.

 

Constraints:

• 1 <= n <= 2 * 105
• 0 <= edges.length <= 2 * 105
• edges[i].length == 2
• 0 <= ui, vi <= n - 1
• ui != vi
• 0 <= source, destination <= n - 1
• There are no duplicate edges.
• There are no self edges.

Solutions

Solution 1

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)

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;
  }
}

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);
  }
};

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)
}

impl Solution {
  pub fn valid_path(n: i32, edges: Vec<Vec<i32>>, source: i32, destination: i32) -> bool {
    let mut disjoint_set: Vec<i32> = vec![0; n as usize];
    // Initialize the set
    for i in 0..n {
      disjoint_set[i as usize] = i;
    }

    // Traverse the edges
    for p_vec in &edges {
      let parent_one = Solution::find(p_vec[0], &mut disjoint_set);
      let parent_two = Solution::find(p_vec[1], &mut disjoint_set);
      disjoint_set[parent_one as usize] = parent_two;
    }

    let p_s = Solution::find(source, &mut disjoint_set);
    let p_d = Solution::find(destination, &mut disjoint_set);

    p_s == p_d
  }

  pub fn find(x: i32, d_set: &mut Vec<i32>) -> i32 {
    if d_set[x as usize] != x {
      d_set[x as usize] = Solution::find(d_set[x as usize], d_set);
    }
    d_set[x as usize]
  }
}

Solution 2

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)

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];
  }
}

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);
  }
};

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)
}