algoadvance

Leetcode 1971. Find if Path Exists in Graph

Problem Statement

You are given an undirected graph with n nodes numbered from 0 to n - 1 and an array of edges where edges[i] = [a_i, b_i] indicates that there is an undirected edge between nodes a_i and b_i. Given two integer nodes start and end, return true if there is a path between start and end otherwise return false.

Example:

Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], start = 0, end = 5
Output: false

Clarifying Questions

  1. Can the edges array be empty?
    • Yes, in which case there are no edges in the graph.
  2. Can there be self-loops in the graph?
    • The problem does not specify, so we will assume there can be.
  3. Can there be multiple edges between two nodes?
    • The problem does not specify, but typically such problems assume simple graphs unless specified.
  4. What should we return if start is the same as end?
    • We should return true since the node is trivially reachable from itself.

Strategy

  1. Graph Representation:
    • Use an adjacency list to represent the graph.
  2. Graph Traversal:
    • Use Depth-First Search (DFS) or Breadth-First Search (BFS) to determine if there is a path from start to end.
  3. Visited Nodes:
    • Keep track of visited nodes to prevent infinite loops.

Code

#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <iostream>

using namespace std;

bool dfs(int start, int end, unordered_map<int, vector<int>>& graph, unordered_set<int>& visited) {
    if (start == end) return true;
    
    visited.insert(start);
    
    for (int neighbor : graph[start]) {
        if (visited.find(neighbor) == visited.end()) {
            if (dfs(neighbor, end, graph, visited)) {
                return true;
            }
        }
    }
    
    return false;
}

bool validPath(int n, vector<vector<int>>& edges, int start, int end) {
    if (start == end) return true;
    
    unordered_map<int, vector<int>> graph;
    
    // Construct the graph
    for (const auto& edge : edges) {
        graph[edge[0]].push_back(edge[1]);
        graph[edge[1]].push_back(edge[0]);
    }
    
    unordered_set<int> visited;
    return dfs(start, end, graph, visited);
}

int main() {
    int n = 6;
    vector<vector<int>> edges = \{\{0,1},{0,2},{3,5},{5,4},{4,3}};
    int start = 0, end = 5;

    bool result = validPath(n, edges, start, end);
    cout << (result ? "true" : "false") << endl;

    return 0;
}

Time Complexity

Thus, the overall time complexity is O(V + E). This is efficient for typical constraints in graph problems where V and E are large.

Explanation

  1. Graph Construction:
    • We build an adjacency list from the given edge list.
  2. DFS to Find Path:
    • We perform a DFS starting from the start node. If we reach the end node, we return true.
    • If all reachable nodes are visited without finding end, we return false.
  3. Handling Edge Cases:
    • If start is equal to end, we immediately return true.

This approach ensures that we efficiently determine if a path exists between two nodes in an undirected graph.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI