Welcome to Subscribe On Youtube

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

• Java
• C++
• Python
• Go
• RenderScript

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

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

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

All Problems

All Solutions