Full Reachability in a Directed Graph

Edited by Charles

Medium · Python · Graph

Problem

You are given a directed graph with n nodes labeled from 1 to n.

The graph is represented by a list of directed edges, where:

[s, t]

represents a directed edge from node s to node t.

Starting from node 1, determine whether every node in the graph can be reached by following the directed edges.

Return:

• 1 if every node can be reached from node 1.
• -1 otherwise.

Example 1

Input:

n = 4
edges = [
    [1, 2],
    [2, 1],
    [1, 3],
    [2, 4]
]

Sample Output

1

Explanation

As shown in the figure, starting from node 1, we can reach nodes 2, 3, and 4. Therefore, all nodes are reachable, and the answer is 1.

The graph contains the following directed edges:

1 → 2
2 → 1
1 → 3
2 → 4

Starting from node 1:

1 → 2
1 → 3
1 → 2 → 4

Therefore, nodes 1, 2, 3, and 4 are all reachable from node 1.

Return:

1

Example 2

Input:

n = 5
edges = [
    [1, 2],
    [2, 3],
    [4, 5]
]

Output:

-1

Explanation:

Starting from node 1, we can reach:

1 → 2 → 3

However, nodes 4 and 5 cannot be reached from node 1.

Therefore, not every node is reachable.

Return:

-1

Example 3

Input:

n = 3
edges = [
    [1, 2],
    [2, 3]
]

Output:

1

Explanation:

Starting from node 1:

1 → 2 → 3

All nodes are reachable from node 1.

Return:

1

Constraints

1 <= n <= 100
1 <= edges.length <= 2000
1 <= edges[i][0], edges[i][1] <= n

Each edge [s, t] represents a directed edge from node s to node t.

Explanation, examples & other approaches

Core idea

This problem is a basic directed graph traversal problem.

Original study notes follow, including intermediate snippets and earlier attempts.

Python

Idea

This problem is a basic directed graph traversal problem.

We are given n nodes and a list of directed edges:

[s, t]

which means there is a directed edge:

s → t

We need to determine whether every node can be reached from node 1.

The main idea is:

Build an adjacency list, start DFS from node 1, and mark every reachable node as visited.

After DFS finishes, if every node from 1 to n has been visited, return 1. Otherwise, return -1.

Step 1: Build the Adjacency List

The input gives us a list of edges:

edges = [
    [1, 2],
    [2, 1],
    [1, 3],
    [2, 4]
]

We convert it into an adjacency list:

graph[1] = [2, 3]
graph[2] = [1, 4]
graph[3] = []
graph[4] = []

We can initialize the graph with:

graph = [[] for _ in range(n + 1)]

Since the nodes are numbered from 1 to n, using size n + 1 makes indexing easier.

Then:

for s, t in edges:
    graph[s].append(t)

Important: This Is a Directed Graph

For an edge:

1 → 2

we only add:

graph[1].append(2)

We should not add:

graph[2].append(1)

unless the reverse edge actually exists in edges.

Step 2: Use a Visited Array

Create:

visit = [False] * (n + 1)

where:

visit[i] = True

means node i can be reached from node 1.

Initially:

visit = [False, False, False, ..., False]

Step 3: DFS

Start DFS from node 1:

dfs(1)

When visiting a node:

visit[i] = True

Then recursively visit all of its outgoing neighbors:

for neighbor in graph[i]:
    dfs(neighbor)

The DFS logic is:

def dfs(i):
    if visit[i]:
        return

    visit[i] = True

    for neighbor in graph[i]:
        dfs(neighbor)

Why Do We Need visit?

The graph may contain cycles.

For example:

1 → 2
↑   ↓
└───┘

Without a visited array, DFS could repeatedly traverse:

1 → 2 → 1 → 2 → 1 → ...

and never stop.

Therefore:

if visit[i]:
    return

prevents us from processing the same node multiple times.

Step 4: Check Whether All Nodes Were Visited

After:

dfs(1)

we check every node:

for i in range(1, n + 1):
    if not visit[i]:
        return -1

If any node was not visited, that node cannot be reached from node 1.

Otherwise:

return 1

Hand Simulation

Consider:

n = 4

edges = [
    [1, 2],
    [2, 1],
    [1, 3],
    [2, 4]
]

The adjacency list is:

1 → [2, 3]
2 → [1, 4]
3 → []
4 → []

Start:

dfs(1)

Visit node 1:

visit:

1 = True
2 = False
3 = False
4 = False

From node 1, visit node 2:

1 → 2

Now:

1 = True
2 = True
3 = False
4 = False

Node 2 has neighbors:

1, 4

Node 1 has already been visited:

if visit[1]:
    return

So we skip it.

Then visit node 4:

1 → 2 → 4

Now:

1 = True
2 = True
3 = False
4 = True

Return to node 1 and visit node 3:

1 → 3

Finally:

1 = True
2 = True
3 = True
4 = True

Every node is reachable, so:

return 1

Unreachable Example

Suppose:

n = 5

edges = [
    [1, 2],
    [2, 3],
    [4, 5]
]

The graph looks like:

1 → 2 → 3

4 → 5

Starting from node 1, DFS can only visit:

1, 2, 3

Therefore:

visit[4] = False
visit[5] = False

When checking all nodes:

if not visit[4]:
    return -1

So the answer is:

-1

General Graph Traversal Pattern

This problem follows a very common graph traversal pattern:

Edge List
   ↓
Build Adjacency List
   ↓
DFS / BFS From Source
   ↓
Mark Visited Nodes
   ↓
Check Reachability

This pattern can be reused for many graph reachability problems.

Complexity Analysis

Let:

V = number of nodes
E = number of edges

Time Complexity

O(V + E)

Each node is visited at most once, and each directed edge is examined at most once.

Space Complexity

O(V + E)

The adjacency list requires:

O(V + E)

The visit array requires:

O(V)

The DFS recursion stack can require up to:

O(V)

in the worst case.

Summary

1. Build an adjacency list from the directed edges.
2. Create a visited array.
3. Start DFS from node 1.
4. Mark every reachable node as visited.
5. Use visited to prevent cycles and repeated traversal.
6. Check nodes 1 through n.
7. If any node is unvisited, return -1.
8. Otherwise, return 1.

The key idea is:

To determine whether all nodes are reachable from a source, traverse the graph from that source and check whether every node has been visited.

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	August 20, 2026

Python solution

from typing import List

class Solution:
    def canReachAllNodes(self, n: int, edges: List[List[int]]) -> int:
        graph = [[] for _ in range(n + 1)]

        for s, t in edges:
            graph[s].append(t)

        visit = [False] * (n + 1)

        def dfs(i):
            if visit[i]:
                return

            visit[i] = True

            for neighbor in graph[i]:
                dfs(neighbor)

        dfs(1)

        for i in range(1, n + 1):
            if not visit[i]:
                return -1

        return 1

---

Back to Day 46 Graph IV · All Algorithm notes