All Paths from Source Lead to Destination

Problem Statement

In this problem, you are given a directed graph represented as a list of edges, where each edge edges[i] = [ai, bi] shows a direct link from node ai to node bi. Besides the graph itself, you are provided two specific nodes: source and destination. Your task is to determine if every possible path starting from the source node ultimately leads exclusively to the destination node under the following conditions:

• There exists at least one valid path from the source to the destination.
• Any potential path that leads to a node with no outward edges must terminate at the destination node.
• The total number of different paths from the source to the destination is finite.

The solution should return true if all paths from the source adhere to these conditions leading to the destination node, otherwise false.

Examples

Example 1

Input:

n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2

Output:

false

Explanation:

It is possible to reach and get stuck on both node 1 and node 2.

Example 2

Input:

n = 4, edges = [[0,1],[0,3],[1,2],[2,1]], source = 0, destination = 3

Output:

false

Explanation:

We have two possibilities: to end at node 3, or to loop over node 1 and node 2 indefinitely.

Example 3

Input:

n = 4, edges = [[0,1],[0,2],[1,3],[2,3]], source = 0, destination = 3

Output:

true

Constraints

• 1 <= n <= 104
• 0 <= edges.length <= 104
• edges.length == 2
• 0 <= ai, bi <= n - 1
• 0 <= source <= n - 1
• 0 <= destination <= n - 1
• The given graph may have self-loops and parallel edges.

Approach and Intuition

Based on the provided examples and constraints, we can derive an approach to solve the task:

1. Graph Representation: Start by representing the graph with an adjacency list. This enables easy traversal and checking outgoing edges for each node.

2. Depth-First Search (DFS) or Breadth-First Search (BFS):

   • Use DFS or BFS to explore all possible paths from the source. This helps in understanding which nodes are accessible from the source and also to detect cycles.
   • During this traversal, also check nodes that have no outgoing edges. Ensure these nodes are the destination node. If any such node isn't, immediately return false.

3. Cycle Detection:

   • Detect cycles in the paths using a visited stack. If a cycle is detected and it doesn't include the destination node or it prevents reaching the destination, return false.
   • If destination is part of a cycle, it must be the only node in its cycle or have a direct cycle (self-loop), such that the traversal is confined only to destination.

4. Path Confirmation:

   • Ensure every reachable node from the source has paths leading solely to the destination. If any node can lead to an alternate path not concluding at destination, or traps in a cyclic loop not involving destination, the condition is not satisfied.

5. Validation:

   • After traversal, if all paths lead from source to destination without inconsistencies like unreachable destination or incorrect terminations, then confirm by returning true.

Complexity: The complexity mainly depends on the number of nodes (n) and edges in the graph given the need to traverse potentially all nodes and edges. With the constraints provided, we ensure the approach remains efficient within these limits.

Solutions

class Solution {
        
    enum State { VISITING, VISITED };
        
    public boolean canReachDestination(int number_of_nodes, int[][] links, int start, int target) {
            
        List<Integer>[] adjacencyList = createGraph(number_of_nodes, links);
        return checkPath(adjacencyList, start, target, new State[number_of_nodes]);
    }
        
    private boolean checkPath(List<Integer>[] adjList, int current, int end, State[] visited) {
            
        if (visited[current] != null) {
            return visited[current] == State.VISITED;
        }
            
        if (adjList[current].isEmpty()) {
            return current == end;
        }
            
        visited[current] = State.VISITING;
            
        for (int neighbor : adjList[current]) {
            if (!checkPath(adjList, neighbor, end, visited)) {
                return false;
            }
        }
            
        visited[current] = State.VISITED;
        return true;
    }
        
    private List<Integer>[] createGraph(int nodes, int[][] connection) {
        List<Integer>[] resultGraph = new List[nodes];
        for (int i = 0; i < nodes; i++) {
            resultGraph[i] = new ArrayList<>();
        }
            
        for (int[] link : connection) {
            resultGraph[link[0]].add(link[1]);
        }
            
        return resultGraph;
    }
}