204. Minimum Number of Vertices to Reach All Nodes

🔗 LeetCode Problem: 1557. Minimum Number of Vertices to Reach All Nodes
📊 Difficulty: Medium
🏷️ Topics: Graph, In-degree, Directed Graph

Problem Statement

Given a directed acyclic graph (DAG), with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [fromi, toi] represents a directed edge from node fromi to node toi.

Find the smallest set of vertices from which all nodes in the graph are reachable. It's guaranteed that a unique solution exists.

Notice that you can return the vertices in any order.

Example 1:

Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]

Visual:
    0 ──→ 1
    │
    ↓
    2 ──→ 5
    ↑
    │
    4 ←── 3

Output: [0,3]

Explanation:
  Starting from 0: Can reach 1, 2, 5
  Starting from 3: Can reach 4, 2, 5
  Together: Can reach all nodes {0,1,2,3,4,5}

  Minimum set: {0, 3}

Example 2:

Input: n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]

Visual:
    0 ─→ 1 ─→ 4
    2 ─↗   ↗
    3 ─────

Output: [0,2,3]

Explanation:
  Node 1 has incoming edges from 0, 2, 3
  Node 4 has incoming edges from 1, 2

  Nodes with NO incoming edges: {0, 2, 3}
  These are the starting points!

  From {0, 2, 3}, we can reach all nodes.

Constraints: - 2 <= n <= 10^5 - 1 <= edges.length <= min(10^5, n * (n - 1) / 2) - edges[i].length == 2 - 0 <= fromi, toi < n - All pairs (fromi, toi) are distinct.

---

🌳 Visual Understanding - The Complete Picture

The Problem We're Solving 🤔

Find MINIMUM starting points to reach ALL nodes: 🎯

This is our FIRST directed graph problem! ➡️

Directed graph: Edges have DIRECTION!
  Edge u → v: Can go from u to v
  But NOT from v to u (unless there's another edge)

The key question:
  Which nodes must we START from?

Example:
    0 → 1 → 2

  Can we start from just node 1?
    From 1: Can reach 2 ✅
    But can't reach 0! ❌ (no incoming path)

  Must start from 0:
    From 0: Can reach 1, 2 ✅

  Minimum starting set: {0}

Key insight: Nodes with NO incoming edges! 🔑

Understanding In-Degree 📊

In-degree = Number of edges COMING INTO a node

Example:
    0 → 1 ← 2
        ↓
        3

  In-degree[0] = 0 (no incoming edges)
  In-degree[1] = 2 (edges from 0 and 2)
  In-degree[2] = 0 (no incoming edges)
  In-degree[3] = 1 (edge from 1)

Nodes with in-degree 0: {0, 2}
  These have NO incoming edges!
  Can't be reached from other nodes!
  MUST be starting points! ✅

Nodes with in-degree > 0: {1, 3}
  These CAN be reached from other nodes!
  Don't need to start from them! ❌

Answer: Nodes with in-degree 0! 🎯

Why This Works - The Proof 💡

Claim: Minimum set = All nodes with in-degree 0

Proof by two parts:

Part 1: Must include ALL nodes with in-degree 0 ✅

  If node u has in-degree 0:
    No edge points TO u
    u cannot be reached from any other node
    Must start from u itself!

  So ALL nodes with in-degree 0 must be in answer.

Part 2: Don't need nodes with in-degree > 0 ❌

  If node v has in-degree > 0:
    At least one edge points TO v (say from u)
    v can be reached from u
    Don't need v as starting point!

  Starting from nodes with in-degree 0 will 
  eventually reach all other nodes.

Therefore: Answer = {nodes with in-degree 0} ✅

Simple and elegant! 🌟

Directed vs Undirected 🔀

This is our FIRST directed graph! Important differences:

UNDIRECTED (Problems 195-203):
    A ─── B

  Edge A-B means:
    Can go A → B
    Can go B → A

  Bidirectional!

DIRECTED (Problem 204):
    A ──→ B

  Edge A → B means:
    Can go A → B
    CANNOT go B → A (unless another edge)

  One-way!

This changes everything:
  - In-degree and out-degree are different!
  - Reachability is directional!
  - New problems to solve!

New concept unlocked! 🎯

---

🧠 The Journey - Building Intuition

Part 1: Understanding "Reachability" in Directed Graphs ➡️

💭 In directed graphs, reachability is ONE-WAY!

Example:
    0 → 1 → 2

  From 0: Can reach {0, 1, 2} ✅
  From 1: Can reach {1, 2} ✅
  From 2: Can reach {2} only ✅

Question: Minimum starting nodes to reach all?

If we start from 0:
  Reach: 0, 1, 2 ✅ All covered!

Answer: {0}

If we start from 1:
  Reach: 1, 2 only
  Missing: 0 ❌

If we start from 2:
  Reach: 2 only
  Missing: 0, 1 ❌

Only starting from 0 works! ✅

What makes 0 special?
  No incoming edges! Nobody points to 0!
  Can't reach 0 from anywhere else!

Part 2: The In-Degree Insight 💡

💭 Let's think about which nodes we MUST start from:

Observation:
  If node u can be reached from node v,
  then we don't need u as a starting point!
  Starting from v will cover u.

Question: Which nodes CAN'T be reached?

Answer: Nodes with NO incoming edges!
  If in-degree[u] = 0:
    No edge points to u
    u is unreachable from other nodes
    MUST start from u!

Example:
    0 → 1 ← 2
        ↓
        3

  in-degree[0] = 0 → Must start from 0! ✅
  in-degree[1] = 2 → Can reach from 0 or 2 ❌
  in-degree[2] = 0 → Must start from 2! ✅
  in-degree[3] = 1 → Can reach from 1 ❌

Starting set: {0, 2} ✅

This always gives minimum set! 🎯

Part 3: Why We Don't Need Other Nodes 🤔

💭 Why are nodes with in-degree > 0 not needed?

Example:
    0 → 1 → 2

  in-degree[1] = 1 (from 0)
  in-degree[2] = 1 (from 1)

Do we need to start from 1?
  NO! Starting from 0 will reach 1 ✅

Do we need to start from 2?
  NO! Starting from 0 will reach 2 ✅

Key insight:
  If we can REACH a node, we don't need to START from it!

  Nodes with in-degree > 0 can be reached!
  So we don't need them as starting points!

Only nodes with in-degree 0 are "unreachable"
and must be starting points! 🔑

Part 4: The Algorithm - Incredibly Simple! ✨

💭 The algorithm is beautifully simple:

STEP 1: Count in-degree for each node
  For each edge u → v:
    in-degree[v]++

STEP 2: Find nodes with in-degree 0
  For each node u:
    If in-degree[u] == 0:
      Add u to answer

STEP 3: Return answer
  That's it! ✅

No complex traversal needed!
No BFS or DFS required!
Just count in-degrees! 🎯

Time: O(E) - one pass through edges
Space: O(n) - in-degree array

Elegant and efficient! 🌟

Part 5: Why This is Guaranteed to Work 📐

💭 Mathematical guarantee:

Given: DAG (Directed Acyclic Graph)
  - No cycles
  - Finite graph

Claim: Nodes with in-degree 0 can reach all nodes

Proof:
  1. DAG must have at least one node with in-degree 0
     (Otherwise, would have cycle)

  2. Any node reachable from a starting point
     doesn't need to be a starting point itself

  3. Since it's a DAG, every node is either:
     - Has in-degree 0 (starting point), OR
     - Reachable from a node with in-degree 0

  4. Therefore: Starting from all nodes with
     in-degree 0 covers all nodes! ✅

This is why answer is unique and correct! 🎯

---

🎯 Approach: In-Degree Counting (Optimal!)

The Key Insight 💡

Nodes with in-degree 0 are unreachable! Must start from them! 🎯 Count in-degree for all nodes (how many edges point TO each node) 📊. Nodes with in-degree = 0 have NO incoming edges, can't be reached from anywhere else, MUST be starting points! ✅ Nodes with in-degree > 0 can be reached, don't need as starts! ❌ Time: O(E) - single pass ⚡, Space: O(n) - in-degree array 📦!

Simplest graph problem yet! 🌟

Complete Implementation

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        // ═══════════════════════════════════════════════════
        // IN-DEGREE APPROACH 📊
        // ═══════════════════════════════════════════════════
        // Nodes with in-degree 0 = unreachable
        // These MUST be starting points!
        // ═══════════════════════════════════════════════════

        // ═══════════════════════════════════════════════════
        // STEP 1: COUNT IN-DEGREE FOR EACH NODE 📊
        // ═══════════════════════════════════════════════════
        // in-degree[i] = number of edges pointing TO node i
        // ═══════════════════════════════════════════════════
        int[] inDegree = new int[n];

        for (List<Integer> edge : edges) {
            int from = edge.get(0);
            int to = edge.get(1);

            // Edge from → to increases in-degree of 'to'
            inDegree[to]++;
        }

        // ═══════════════════════════════════════════════════
        // STEP 2: COLLECT NODES WITH IN-DEGREE 0 🎯
        // ═══════════════════════════════════════════════════
        // These nodes have NO incoming edges
        // Cannot be reached from other nodes
        // MUST be starting points!
        // ═══════════════════════════════════════════════════
        List<Integer> result = new ArrayList<>();

        for (int node = 0; node < n; node++) {
            if (inDegree[node] == 0) {
                result.add(node);
            }
        }

        return result;  // Minimum starting set! ✅
    }
}

Why This Works 🎯

In-degree 0 = Unreachable: 📊 - No edges point to these nodes - Cannot be reached from any other node - Must include in starting set!

In-degree > 0 = Reachable: ✅ - At least one edge points to these nodes - Can be reached from other nodes - Don't need as starting points!

Guaranteed minimum: 🔑 - Can't be smaller (all in-degree 0 nodes required) - Don't need more (in-degree 0 nodes reach all others) - Unique optimal solution!

No graph traversal needed: ⚡ - Don't need BFS/DFS - Just count in-degrees - Simple and fast!

---

🔍 Detailed Dry Run

Let's trace on:

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

Visual:
    0 ──→ 1
    │
    ↓
    2 ──→ 5
    ↑
    │
    4 ←── 3

╔══════════════════════════════════════════════════════════════╗
║                  STEP 1: COUNT IN-DEGREES                    ║
╚══════════════════════════════════════════════════════════════╝

Initialize:
  inDegree = [0, 0, 0, 0, 0, 0]

Process edge [0, 1]:
  Edge: 0 → 1
  inDegree[1]++
  inDegree = [0, 1, 0, 0, 0, 0]

Process edge [0, 2]:
  Edge: 0 → 2
  inDegree[2]++
  inDegree = [0, 1, 1, 0, 0, 0]

Process edge [2, 5]:
  Edge: 2 → 5
  inDegree[5]++
  inDegree = [0, 1, 1, 0, 0, 1]

Process edge [3, 4]:
  Edge: 3 → 4
  inDegree[4]++
  inDegree = [0, 1, 1, 0, 1, 1]

Process edge [4, 2]:
  Edge: 4 → 2
  inDegree[2]++
  inDegree = [0, 1, 2, 0, 1, 1]

Final in-degrees:
  Node 0: inDegree = 0 ⭐
  Node 1: inDegree = 1
  Node 2: inDegree = 2
  Node 3: inDegree = 0 ⭐
  Node 4: inDegree = 1
  Node 5: inDegree = 1

╔══════════════════════════════════════════════════════════════╗
║            STEP 2: FIND NODES WITH IN-DEGREE 0              ║
╚══════════════════════════════════════════════════════════════╝

Check node 0:
  inDegree[0] = 0 ✅
  Add to result: [0]

Check node 1:
  inDegree[1] = 1 ❌
  Skip (can be reached)

Check node 2:
  inDegree[2] = 2 ❌
  Skip (can be reached)

Check node 3:
  inDegree[3] = 0 ✅
  Add to result: [0, 3]

Check node 4:
  inDegree[4] = 1 ❌
  Skip (can be reached)

Check node 5:
  inDegree[5] = 1 ❌
  Skip (can be reached)

Result: [0, 3]

╔══════════════════════════════════════════════════════════════╗
║                    VERIFICATION                              ║
╠══════════════════════════════════════════════════════════════╣
║                                                              ║
║  Starting from {0, 3}, can we reach all nodes?              ║
║                                                              ║
║  From node 0:                                                ║
║    0 → 1 (direct edge)                                       ║
║    0 → 2 (direct edge)                                       ║
║    0 → 2 → 5 (path)                                          ║
║    Reached from 0: {0, 1, 2, 5} ✅                          ║
║                                                              ║
║  From node 3:                                                ║
║    3 → 4 (direct edge)                                       ║
║    3 → 4 → 2 (path)                                          ║
║    3 → 4 → 2 → 5 (path)                                      ║
║    Reached from 3: {3, 4, 2, 5} ✅                          ║
║                                                              ║
║  Combined: {0, 1, 2, 3, 4, 5} = All nodes! ✅               ║
║                                                              ║
║  Can we use fewer starting nodes?                            ║
║    No! Both 0 and 3 have in-degree 0                        ║
║    Cannot reach them from other nodes                        ║
║    Must include both! ✅                                     ║
║                                                              ║
║  Answer: [0, 3] is minimal and correct! 🎉                  ║
║                                                              ║
╚══════════════════════════════════════════════════════════════╝

🔑 Key Observations:

1. In-degree counting is simple: 📊 One pass through edges

2. Nodes with in-degree 0 identified: ⭐ Only 0 and 3

3. No graph traversal needed: ⚡ Just array lookup

4. Result is minimal: 🎯 Can't be smaller

5. Verification confirms: ✅ Can reach all nodes from {0, 3}

---

📊 Complexity Analysis

Time Complexity: O(E) ⚡

Where E = number of edges

Step 1: Count in-degrees
  Iterate through all edges: O(E)

Step 2: Find nodes with in-degree 0
  Iterate through all nodes: O(n)

Total: O(E + n) = O(E)
  (Since E ≥ n-1 in connected DAG)

Example: E = 10000, n = 1000
  Operations: ~10000 (very fast!) ✅

Optimal! Can't do better! 🌟

Space Complexity: O(n) 📦

In-degree array: O(n)
Result list: O(n) worst case

Total: O(n) 📦

Example: n = 1000
  Extra space: 1000 integers

Very efficient! 🌟

---

🎯 Pattern Recognition

Directed Graph Pattern 🎯

// Template for directed graph problems
class Solution {
    public List<Integer> directedGraphProblem(int n, int[][] edges) {
        // STEP 1: Calculate in-degrees and/or out-degrees
        int[] inDegree = new int[n];
        int[] outDegree = new int[n];

        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];

            outDegree[from]++;  // Edge leaving 'from'
            inDegree[to]++;     // Edge entering 'to'
        }

        // STEP 2: Process based on degree information
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            // Different problems check different conditions:
            // - In-degree = 0 (this problem)
            // - Out-degree = 0 (leaf nodes)
            // - In-degree = out-degree (Eulerian path)
            if (conditionCheck(inDegree[i], outDegree[i])) {
                result.add(i);
            }
        }

        return result;
    }
}

When to Use In-Degree 📊

✅ Perfect for:
  • Finding starting points (in-degree = 0)
  • Finding endpoints (out-degree = 0)
  • Topological sort prerequisites
  • Dependency analysis
  • Course scheduling

🔍 Recognition keywords:
  • "Directed graph"
  • "Reachable from"
  • "Starting points"
  • "No incoming edges"
  • "Dependencies"

📊 Pattern characteristics:
  • Directed edges (one-way)
  • Counting connections
  • No traversal needed
  • Simple array operations

Related LeetCode Problems 📚

Direct Applications:

1. Course Schedule II (LC 210) - Medium 📚 • What's similar: Directed graph, in-degree counting 📊 • What's different: Topological sort, cycle detection ✅ • Key insight: Process nodes with in-degree 0 first! 💡

2. All Ancestors of a Node (LC 2192) - Medium 🌳 • What's similar: Directed graph, reachability 🔗 • What's different: Find ALL ancestors, not just starts ✅ • Key insight: Reverse DFS from each node! 🎯

3. Find Eventual Safe States (LC 802) - Medium 🛡️ • What's similar: Directed graph, reachability 🌊 • What's different: Find nodes leading to terminals ✅ • Key insight: Out-degree = 0 are safe, work backwards! 💡

---

📝 Quick Revision Notes

🎯 Core Concept

Minimum Vertices = nodes with in-degree 0 (no incoming edges)! 📊 First directed graph problem - edges have direction! ➡️ Key insight: Nodes with in-degree = 0 are unreachable from others, MUST be starting points! ✅ Nodes with in-degree > 0 can be reached, don't need as starts! ❌ Algorithm: Count in-degrees, collect all nodes with in-degree = 0! Time: O(E) - single pass ⚡, Space: O(n) - array only 📦!

⚡ Quick Implementation

import java.util.ArrayList;
import java.util.List;

public class Solution {
  public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
    List<Integer> res = new ArrayList<>();
    // Key steps:
    // 1. Calculate indegrees
    int[] indegrees = new int[n];
    for (List<Integer> curr : edges) {
      indegrees[curr.get(1)]++;
    }

    for (int i = 0; i < n; i++) {
      if (indegrees[i] == 0) {
        res.add(i);
      }
    }

    return res;
  }

  public static void main(String[] args) {
    Solution s = new Solution();

    System.out
        .println(
            s.findSmallestSetOfVertices(6,
                List.of(List.of(0, 1), List.of(0, 2), List.of(2, 5), List.of(3, 4), List.of(4, 2))));

    System.out
        .println(
            s.findSmallestSetOfVertices(6,
                List.of(List.of(0, 1), List.of(2, 1), List.of(3, 1), List.of(1, 4), List.of(2, 4))));
  }
}

🔑 Key Insights

In-Degree Concept: 📊

In-degree = Number of edges COMING INTO a node

Example:
  Edge: A → B

  Out-degree[A]++ (leaving A)
  In-degree[B]++  (entering B)

For this problem:
  Only care about in-degree!

In-degree = 0 → Must start here ✅
In-degree > 0 → Can reach ❌

Why In-Degree 0 is Minimum: 🔑

Claim: Answer = {nodes with in-degree 0}

Why we need ALL of them:
  Node with in-degree 0 has NO incoming edges
  Cannot be reached from any other node
  Must include in starting set! ✅

Why we don't need others:
  Node with in-degree > 0 has incoming edges
  Can be reached from some other node
  Don't need as starting point! ❌

This is minimal AND sufficient! 🎯

Directed vs Undirected: 🔀

NEW CONCEPT: Directed graphs!

Undirected:
  A ─── B
  Can go both ways: A↔B

Directed:
  A ──→ B
  One way only: A→B (not B→A)

This changes:
  • In-degree ≠ out-degree
  • Reachability is directional
  • New types of problems!

First of many directed graph problems! 🌟

No Traversal Needed: ⚡

Unlike previous problems:
  • No BFS required!
  • No DFS required!
  • No graph traversal!

Just:
  1. Count in-degrees (one pass)
  2. Check which are 0

Simplest graph algorithm yet! ✨

Time: O(E) - linear!
Space: O(n) - just array!

🎪 Memory Aid

"In-degree zero, must start here" 🎯
"No incoming edge, crystal clear" 📊
"Others reachable, we don't need" ❌
"Count and collect, simple indeed!" ⚡ ✨

⚠️ Don't Forget

• Directed graph - edges have direction! ➡️
• In-degree only - count edges COMING IN! 📊
• Edge direction - from → to, increment to's in-degree! 🎯
• Zero means unreachable - must include! ✅
• No traversal needed - just counting! ⚡
• Result is unique - guaranteed by problem! 🔑

---

🎉 Congratulations!

You've learned about DIRECTED GRAPHS - a new frontier! 🌟

What You Learned:

✅ Directed graphs - edges have direction! ➡️
✅ In-degree concept - edges coming INTO node! 📊
✅ Out-degree concept - edges leaving FROM node! 🚀
✅ Reachability analysis - directional paths! 🔗
✅ Simple counting algorithm - no traversal! ⚡
✅ Minimal set problem - optimization! 🎯

The Beautiful Insight:

Problem Categories We've Mastered:

UNDIRECTED GRAPHS (195-203):
  ├─ Connected components
  ├─ Cycle detection
  ├─ Union-Find patterns
  └─ Bipartite checking

DIRECTED GRAPHS (204+): ⭐ NEW!
  ├─ In-degree/Out-degree
  ├─ Reachability
  ├─ Topological ordering
  └─ Dependency analysis

Directed graphs unlock new problems! 🔑

Key differences:
  • One-way edges
  • In-degree ≠ out-degree
  • Directional reachability
  • Topological concepts

This problem introduces:
  ✅ Directed graph basics
  ✅ In-degree counting
  ✅ Simple but powerful pattern

More directed graph problems coming! 🚀

From Undirected to Directed:

Journey so far:

Problems 195-203: Undirected graphs
  • Bidirectional edges
  • Symmetric relationships
  • BFS/DFS/Union-Find

Problem 204: First directed graph! ⭐
  • One-way edges
  • Asymmetric relationships
  • Degree analysis

New toolkit acquired:
  ✅ In-degree counting
  ✅ Out-degree tracking
  ✅ Directional thinking

Foundation set for:
  • Topological sort
  • DAG problems
  • Dependency graphs
  • Course scheduling

Exciting new territory! 🌟

Twenty-seven problems completed! 🎉
Directed graphs introduced! First in-degree problem mastered! New graph category unlocked! 💪✨🎯📊➡️🔑🌟