All Paths from Source Lead to Destination

All Paths from Source Lead to Destination - Problem

Given the edges of a directed graph where edges[i] = [ai, bi] indicates there is an edge between nodes ai and bi, and two nodes source and destination of this graph, determine whether or not all paths starting from source eventually end at destination.

This means:

At least one path exists from the source node to the destination node
If a path exists from the source node to a node with no outgoing edges, then that node is equal to destination
The number of possible paths from source to destination is a finite number

Return true if and only if all roads from source lead to destination.

Input & Output

Example 1 — Valid Path Structure

$ Input: edges = [[0,1],[0,2],[1,3],[2,3]], source = 0, destination = 3

› Output: true

💡 Note: There are two paths from source 0 to destination 3: 0→1→3 and 0→2→3. Both paths end at destination 3, and there are no cycles, so return true.

Example 2 — Wrong Destination

$ Input: edges = [[0,1],[0,2],[1,3],[2,3]], source = 0, destination = 2

› Output: false

💡 Note: Path 0→1→3 ends at node 3, not at the specified destination 2. Since not all paths lead to destination, return false.

Example 3 — Cycle Present

$ Input: edges = [[0,1],[1,1],[1,2]], source = 0, destination = 2

› Output: false

💡 Note: There is a self-loop at node 1 (1→1), creating an infinite cycle. This violates the finite paths requirement, so return false.

Constraints

1 ≤ edges.length ≤ 10⁴
edges[i].length == 2
0 ≤ ai, bi ≤ 10³
0 ≤ source ≤ 10³
0 ≤ destination ≤ 10³

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Directed graph with edges, source node, and destination node

Path Validation

Check all possible paths using DFS with cycle detection

Result

True if all paths end at destination with no infinite loops

Key Takeaway

🎯 Key Insight: Use three-state DFS (WHITE/GRAY/BLACK) to detect cycles while ensuring all leaf nodes equal the destination

Asked in

G Google 15 f Facebook 12 M Microsoft 8

The optimal approach uses DFS with three-color state tracking to detect cycles and validate that all paths from source lead to destination. The key insight is using GRAY state to detect back edges (cycles) while ensuring leaf nodes equal the destination. Time: O(V + E), Space: O(V + E)

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Three States	O(V + E)	O(V + E)	Use three-color DFS to detect cycles and validate all paths
Brute Force DFS	O(2^N)	O(N)	Explore every possible path from source using simple DFS

DFS with Three States — Algorithm Steps

Initialize all nodes as WHITE (unvisited)
Start DFS from source, mark as GRAY
For each neighbor, recursively check paths
Mark node BLACK when all children processed
Return false if cycle detected or wrong endpoint

Visualization

Tap to expand

Step-by-Step Walkthrough

Color Nodes

WHITE=unvisited, GRAY=visiting, BLACK=done

DFS Traversal

Mark GRAY when entering, BLACK when leaving

Cycle Check

If we reach GRAY node, cycle detected

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_NODES 10000
#define WHITE 0
#define GRAY 1
#define BLACK 2

int graph[MAX_NODES][MAX_NODES];
int outDegree[MAX_NODES];
int color[MAX_NODES];

bool dfs(int node, int destination) {
    color[node] = GRAY;
    
    if (outDegree[node] == 0) {
        color[node] = BLACK;
        return node == destination;
    }
    
    for (int i = 0; i < outDegree[node]; i++) {
        int neighbor = graph[node][i];
        if (color[neighbor] == GRAY) return false;
        if (color[neighbor] == WHITE && !dfs(neighbor, destination)) return false;
    }
    
    color[node] = BLACK;
    return true;
}

bool solution(int edges[][2], int edgesSize, int source, int destination) {
    memset(outDegree, 0, sizeof(outDegree));
    memset(color, WHITE, sizeof(color));
    
    for (int i = 0; i < edgesSize; i++) {
        int from = edges[i][0];
        int to = edges[i][1];
        graph[from][outDegree[from]++] = to;
    }
    
    return dfs(source, destination);
}

int main() {
    int edges[1000][2];
    int edgesSize = 0;
    int source, destination;
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse edges (simplified)
    char* ptr = line;
    while (*ptr && edgesSize < 1000) {
        if (*ptr == '[' && *(ptr+1) != '[') {
            sscanf(ptr+1, "%d,%d", &edges[edgesSize][0], &edges[edgesSize][1]);
            edgesSize++;
        }
        ptr++;
    }
    
    scanf("%d", &source);
    scanf("%d", &destination);
    
    bool result = solution(edges, edgesSize, source, destination);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(V + E)

Each vertex and edge visited at most once during DFS traversal

✓ Linear Growth

Space Complexity

O(V + E)

Adjacency list storage plus recursion stack depth up to V nodes

✓ Linear Space

35.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with Three States — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler