Skip to content

Path In Directed Graph

Logical Breakdown

  • [ ] Subproblem Identification:
  • [ ] Optimal Substructure:
  • [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
  • [ ] Optimization: (Matrix Exponentiation if 'A' is huge)

Mathematical Rigor

State Definition

Let \(dp[i]\) be the state for the \(i\)-th subproblem.

Recurrence Relation

\[ dp[i] = ... \]

Visualization

graph TD A["Current State"] --> B["Previous State 1"] A --> C["Previous State 2"]

Complexity Analysis

Approach Time Complexity Space Complexity
Iterative DP \(O(N)\) \(O(1)\)

Code Reference

package com.dsa.graphs;

/* * ============================================================================================ * PROBLEM: Path in Directed Graph * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given a directed graph having A nodes (1 to A) and an array B of edges. * Determine if there exists a path from Node 1 to Node A. * Return 1 if a path exists, 0 otherwise. * * --------------------- * 2. Logical Breakdown * --------------------- * This is a classic Reachability problem. * We can use either Breadth-First Search (BFS) or Depth-First Search (DFS). * * Approach (BFS): * 1. Build an Adjacency List from the input edges. * 2. Initialize a Queue and a 'visited' array. * 3. Add Source (1) to Queue and mark visited. * 4. While Queue is not empty: * - Dequeue current node 'u'. * - If 'u' == A (Destination), return 1. * - For each neighbor 'v' of 'u': * - If 'v' is not visited, enqueue 'v' and mark visited. * 5. If Queue becomes empty and A is not reached, return 0. * * --------------------- * 3. Constraints & Complexity * --------------------- * Time Complexity: O(V + E) * - Building Graph: O(E) * - BFS Traversal: O(V + E) in worst case. * Space Complexity: O(V + E) * - Adjacency List: O(V + E) * - Visited Array & Queue: O(V) * * ============================================================================================ / public class PathInDirectedGraph { public int solve(int A, int[][] edges3) { // TODO: Implement solution return 0; } }