First Depth First Search

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;

import java.util.*;

/* * ============================================================================================ * PROBLEM: First Depth First Search (Reachability) * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * You are given N towns (1 to N). There are M one-way roads between towns. * You are given a starting town S and a destination town D. * Check if it is possible to reach town D from town S. * * --------------------- * 2. Logical Breakdown * --------------------- * Standard DFS Implementation. * * Recursive DFS(u): * 1. Mark 'u' as visited. * 2. If 'u' == Destination, return true. * 3. For each neighbor 'v' of 'u': * - If 'v' is not visited: * - If DFS(v) returns true, propagate true up the stack. * 4. Return false if no path found from 'u'. * * --------------------- * 3. Complexity * --------------------- * Time: O(V + E) * Space: O(V) (Recursion Stack + Visited Array) + O(E) (Graph Storage). * * ============================================================================================ / public class FirstDepthFirstSearch { public int solve(int A) { // TODO: Implement solution return 0; }

public int isReachable(int i, int[] from, int[] to, int i1, int i2) {
    return 1;
}

}