LeetCode 3383 - Minimum Runes to Add to Cast Spell

We are given a directed graph with n focus points, numbered from 0 to n - 1. Some focus points already contain magic crystals. These are the starting sources of magic energy. Directed runes represent one-way magic flow between focus points.

leetcodehardarraydepth-first-searchbreadth-first-searchunion-findgraph-theorytopological-sort

LeetCode Problem 3383

Difficulty: 🔴 Hard
Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory, Topological Sort

Solution

Problem Understanding

We are given a directed graph with n focus points, numbered from 0 to n - 1.

Some focus points already contain magic crystals. These are the starting sources of magic energy. Directed runes represent one-way magic flow between focus points. If there is a rune from u to v, then magic can travel from u to v.

The goal is to ensure that every focus point is valid under one of these conditions:

  1. The focus point directly contains a crystal.
  2. The focus point can receive magic from another focus point through directed paths.

We are allowed to add new directed runes, and we must compute the minimum number of runes needed.

The important observation is that magic propagation is transitive. If a crystal can reach node A, and A can reach B, then B also receives magic. Therefore, the problem becomes:

Make every node reachable from at least one crystal, using the fewest additional directed edges.

The input consists of:

  • n, the number of nodes.
  • crystals, a list of source nodes.
  • flowFrom[i] -> flowTo[i], the existing directed edges.

The constraints are large:

  • Up to 10^5 nodes.
  • Up to 2 * 10^5 edges.

This immediately tells us that any algorithm worse than roughly linear or near-linear time will likely time out. We need an algorithm around O(n + m) where m is the number of edges.

Several edge cases are important:

  • The graph may already be fully reachable from crystals, answer is 0.
  • The graph may contain disconnected strongly connected components.
  • Cycles are common, so naive traversal logic can repeatedly revisit nodes.
  • Multiple crystals may already cover overlapping regions.
  • Some nodes may have no incoming or outgoing edges at all.
  • The graph is directed, so reachability is not symmetric.

The directed nature of the graph is the key difficulty.

Approaches

Brute Force Approach

A naive approach would repeatedly search for unreachable nodes and try adding edges greedily.

For every node not reachable from crystals, we could attempt to connect it from some reachable node, then recompute reachability using DFS or BFS. We would continue until all nodes become reachable.

This approach is correct because eventually every disconnected region receives a connection. However, it is far too slow because repeated graph traversals are expensive.

If there are many disconnected regions, we may perform O(n) traversals, each costing O(n + m). That leads to O(n * (n + m)), which is infeasible for 10^5 nodes.

The deeper issue is that the graph may contain cycles. Treating nodes individually ignores the structure of strongly connected components.

Key Insight

Inside a strongly connected component, every node can already reach every other node.

Therefore, if one node in an SCC receives magic, the entire SCC automatically receives magic.

This suggests compressing the graph into SCCs. After condensation:

  • Each SCC becomes a single node.
  • The condensed graph is a Directed Acyclic Graph, DAG.
  • We only need to ensure every SCC is reachable from at least one crystal SCC.

Now consider SCCs that are not reachable from crystal SCCs.

In a DAG, any SCC with indegree 0 among the unreached SCCs cannot receive magic from another unreached SCC. Therefore, each such SCC requires at least one added edge.

Conversely, adding one edge into each zero-indegree unreached SCC is sufficient.

So the answer becomes:

Count the unreached SCCs whose indegree inside the unreached subgraph is zero.

This transforms a difficult graph problem into a clean SCC condensation problem.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * (n + m)) O(n + m) Repeated reachability recomputation
Optimal O(n + m) O(n + m) SCC compression plus DAG indegree counting

Algorithm Walkthrough

Step 1: Build the Graph

Construct adjacency lists for the directed graph and its reverse graph.

The reverse graph is needed for Kosaraju's SCC algorithm.

Step 2: Run First DFS for Finishing Order

Perform DFS on the original graph.

After exploring all descendants of a node, append it to an ordering list.

This ordering captures nodes by finishing time. In Kosaraju's algorithm, processing nodes in reverse finishing order allows SCC extraction correctly.

Step 3: Run DFS on the Reverse Graph

Process nodes in reverse finishing order.

For each unvisited node, perform DFS on the reversed graph. Every node reached belongs to the same SCC.

Assign every node an SCC identifier.

At the end:

  • component[node] tells which SCC the node belongs to.
  • componentCount is the number of SCCs.

Step 4: Mark SCCs Reachable from Crystals

Every crystal belongs to some SCC.

These SCCs are the starting sources of magic.

Run DFS or BFS on the condensed SCC graph indirectly by traversing original edges:

  • Start from all crystal nodes.
  • Mark all reachable nodes.
  • Convert those nodes into reachable SCCs.

Alternatively, we can directly mark reachable SCCs during traversal.

Step 5: Compute Indegree Among Unreachable SCCs

Now consider only SCCs that are not reachable from crystals.

For every edge u -> v:

  • Let cu = component[u]
  • Let cv = component[v]

If:

  • cu != cv
  • both SCCs are unreachable

then increment indegree of cv.

This builds the DAG structure among unreachable SCCs.

Step 6: Count Zero-Indegree Unreachable SCCs

Every unreachable SCC with indegree 0 needs one new rune.

Count such SCCs and return the total.

Why it works

After SCC compression, the graph becomes a DAG. Any SCC reachable from a crystal already satisfies the requirement.

For the remaining SCCs, an SCC with indegree greater than zero can receive magic from another unreachable SCC after that SCC is connected. However, a zero-indegree unreachable SCC has no incoming path from any other unreachable SCC, so it must receive a direct new connection.

Adding one edge to each such SCC is both necessary and sufficient, which guarantees optimality.

Python Solution

from typing import List
from collections import deque

class Solution:
    def minRunesToAdd(
        self,
        n: int,
        crystals: List[int],
        flowFrom: List[int],
        flowTo: List[int]
    ) -> int:
        
        graph = [[] for _ in range(n)]
        reverse_graph = [[] for _ in range(n)]

        for u, v in zip(flowFrom, flowTo):
            graph[u].append(v)
            reverse_graph[v].append(u)

        # First pass of Kosaraju
        visited = [False] * n
        order = []

        def dfs1(node: int) -> None:
            visited[node] = True

            for neighbor in graph[node]:
                if not visited[neighbor]:
                    dfs1(neighbor)

            order.append(node)

        for node in range(n):
            if not visited[node]:
                dfs1(node)

        # Second pass of Kosaraju
        component = [-1] * n
        component_count = 0

        def dfs2(node: int, comp_id: int) -> None:
            component[node] = comp_id

            for neighbor in reverse_graph[node]:
                if component[neighbor] == -1:
                    dfs2(neighbor, comp_id)

        for node in reversed(order):
            if component[node] == -1:
                dfs2(node, component_count)
                component_count += 1

        # Find all nodes reachable from crystals
        reachable_nodes = [False] * n
        queue = deque()

        for crystal in crystals:
            if not reachable_nodes[crystal]:
                reachable_nodes[crystal] = True
                queue.append(crystal)

        while queue:
            node = queue.popleft()

            for neighbor in graph[node]:
                if not reachable_nodes[neighbor]:
                    reachable_nodes[neighbor] = True
                    queue.append(neighbor)

        # Mark reachable SCCs
        reachable_components = [False] * component_count

        for node in range(n):
            if reachable_nodes[node]:
                reachable_components[component[node]] = True

        # Compute indegree among unreachable SCCs
        indegree = [0] * component_count

        for u, v in zip(flowFrom, flowTo):
            cu = component[u]
            cv = component[v]

            if cu == cv:
                continue

            if reachable_components[cu]:
                continue

            if reachable_components[cv]:
                continue

            indegree[cv] += 1

        # Count unreachable SCCs with indegree 0
        answer = 0

        for comp_id in range(component_count):
            if reachable_components[comp_id]:
                continue

            if indegree[comp_id] == 0:
                answer += 1

        return answer

The implementation begins by constructing both the original graph and the reversed graph. Kosaraju's algorithm requires both directions.

The first DFS computes finishing order. Nodes are appended after all descendants are explored, which creates the correct reverse topological processing order for SCC discovery.

The second DFS runs on the reversed graph. Each traversal identifies one SCC and assigns all contained nodes the same component identifier.

After SCC decomposition, the code performs BFS starting from every crystal node. This identifies all graph nodes that already receive magic.

Those reachable nodes are mapped into reachable SCCs.

Next, the algorithm scans every original edge. Whenever an edge connects two different unreachable SCCs, the destination SCC gains indegree.

Finally, every unreachable SCC with indegree zero contributes one required rune.

Go Solution

package main

func minRunesToAdd(n int, crystals []int, flowFrom []int, flowTo []int) int {
	graph := make([][]int, n)
	reverseGraph := make([][]int, n)

	for i := 0; i < len(flowFrom); i++ {
		u := flowFrom[i]
		v := flowTo[i]

		graph[u] = append(graph[u], v)
		reverseGraph[v] = append(reverseGraph[v], u)
	}

	// First pass of Kosaraju
	visited := make([]bool, n)
	order := make([]int, 0)

	var dfs1 func(int)

	dfs1 = func(node int) {
		visited[node] = true

		for _, neighbor := range graph[node] {
			if !visited[neighbor] {
				dfs1(neighbor)
			}
		}

		order = append(order, node)
	}

	for node := 0; node < n; node++ {
		if !visited[node] {
			dfs1(node)
		}
	}

	// Second pass of Kosaraju
	component := make([]int, n)

	for i := 0; i < n; i++ {
		component[i] = -1
	}

	componentCount := 0

	var dfs2 func(int, int)

	dfs2 = func(node int, compID int) {
		component[node] = compID

		for _, neighbor := range reverseGraph[node] {
			if component[neighbor] == -1 {
				dfs2(neighbor, compID)
			}
		}
	}

	for i := n - 1; i >= 0; i-- {
		node := order[i]

		if component[node] == -1 {
			dfs2(node, componentCount)
			componentCount++
		}
	}

	// BFS from crystals
	reachableNodes := make([]bool, n)
	queue := make([]int, 0)

	for _, crystal := range crystals {
		if !reachableNodes[crystal] {
			reachableNodes[crystal] = true
			queue = append(queue, crystal)
		}
	}

	head := 0

	for head < len(queue) {
		node := queue[head]
		head++

		for _, neighbor := range graph[node] {
			if !reachableNodes[neighbor] {
				reachableNodes[neighbor] = true
				queue = append(queue, neighbor)
			}
		}
	}

	// Reachable SCCs
	reachableComponents := make([]bool, componentCount)

	for node := 0; node < n; node++ {
		if reachableNodes[node] {
			reachableComponents[component[node]] = true
		}
	}

	// Indegree among unreachable SCCs
	indegree := make([]int, componentCount)

	for i := 0; i < len(flowFrom); i++ {
		cu := component[flowFrom[i]]
		cv := component[flowTo[i]]

		if cu == cv {
			continue
		}

		if reachableComponents[cu] {
			continue
		}

		if reachableComponents[cv] {
			continue
		}

		indegree[cv]++
	}

	// Count zero indegree SCCs
	answer := 0

	for compID := 0; compID < componentCount; compID++ {
		if reachableComponents[compID] {
			continue
		}

		if indegree[compID] == 0 {
			answer++
		}
	}

	return answer
}

The Go implementation closely mirrors the Python solution.

Slices are used for adjacency lists and queues. Instead of using a dedicated queue structure, the BFS uses a slice with a moving head index, which avoids repeated shifting operations.

The SCC assignment array is initialized with -1 because Go integers default to 0.

No integer overflow concerns exist because all counts remain within standard 32-bit integer range.

Worked Examples

Example 1

n = 6
crystals = [0]

Edges:
0 -> 1
1 -> 2
2 -> 3
3 -> 0

Step 1: SCC Decomposition

Nodes 0,1,2,3 form one SCC because they are mutually reachable.

Nodes 4 and 5 are isolated SCCs.

Node SCC
0 A
1 A
2 A
3 A
4 B
5 C

Step 2: Reachability from Crystals

Crystal node 0 reaches:

0 -> 1 -> 2 -> 3

Reachable SCCs:

SCC Reachable
A Yes
B No
C No

Step 3: Indegree Among Unreachable SCCs

There are no edges into SCC B or SCC C.

SCC Indegree
B 0
C 0

Both require direct connections.

Answer = 2.

Example 2

n = 7
crystals = [3,5]

Edges:
0 -> 1
1 -> 2
2 -> 0
3 -> 4
5 -> 6

Step 1: SCCs

Nodes SCC
0,1,2 A
3 B
4 C
5 D
6 E

Step 2: Reachability

Crystal 3 reaches 4.

Crystal 5 reaches 6.

Reachable SCCs:

SCC Reachable
A No
B Yes
C Yes
D Yes
E Yes

Step 3: Unreachable SCC Indegree

Only SCC A remains unreachable.

No unreachable SCC points into it.

SCC Indegree
A 0

Therefore answer = 1.

Adding one edge such as 4 -> 2 makes the entire SCC reachable.

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) SCC decomposition and traversals each process every node and edge a constant number of times
Space O(n + m) Adjacency lists, SCC arrays, visited arrays, and queues

The algorithm is linear in the size of the graph. Kosaraju's algorithm performs two DFS passes, each visiting every node and edge once. The BFS reachability pass and indegree computation are also linear.

This efficiency is necessary for handling graphs with up to 10^5 vertices and 2 * 10^5 edges.

Test Cases

sol = Solution()

# Example 1
assert sol.minRunesToAdd(
    6,
    [0],
    [0, 1, 2, 3],
    [1, 2, 3, 0]
) == 2  # two isolated nodes need direct connections

# Example 2
assert sol.minRunesToAdd(
    7,
    [3, 5],
    [0, 1, 2, 3, 5],
    [1, 2, 0, 4, 6]
) == 1  # one unreachable SCC

# Already fully reachable
assert sol.minRunesToAdd(
    4,
    [0],
    [0, 1, 2],
    [1, 2, 3]
) == 0  # all nodes reachable from crystal

# Completely disconnected graph
assert sol.minRunesToAdd(
    5,
    [0],
    [],
    []
) == 4  # every non-crystal node needs a connection

# Multiple SCCs chained together
assert sol.minRunesToAdd(
    6,
    [0],
    [0, 1, 2, 3, 4],
    [1, 0, 3, 2, 5]
) == 1  # one disconnected SCC chain

# All nodes are crystals
assert sol.minRunesToAdd(
    5,
    [0, 1, 2, 3, 4],
    [],
    []
) == 0  # nothing needed

# Single large SCC without crystal
assert sol.minRunesToAdd(
    4,
    [0],
    [1, 2, 3],
    [2, 3, 1]
) == 1  # one SCC disconnected from crystal

# Multiple disconnected SCC roots
assert sol.minRunesToAdd(
    8,
    [0],
    [1, 2, 4, 5],
    [2, 1, 5, 4]
) == 3  # three unreachable SCC roots

# DAG of unreachable SCCs
assert sol.minRunesToAdd(
    6,
    [0],
    [1, 2, 3],
    [2, 3, 4]
) == 1  # only first unreachable SCC needs connection

# Cycle reachable from crystal
assert sol.minRunesToAdd(
    5,
    [0],
    [0, 1, 2, 3],
    [1, 2, 3, 1]
) == 1  # node 4 isolated
Test Why
Example 1 Validates isolated nodes outside reachable SCC
Example 2 Validates SCC compression logic
Fully reachable graph Ensures answer can be zero
Completely disconnected graph Tests many isolated nodes
Multiple SCC chains Tests DAG behavior
All nodes are crystals Confirms trivial zero case
Large disconnected SCC Ensures SCC treated as one unit
Multiple SCC roots Tests counting zero-indegree SCCs
Unreachable DAG Verifies only source SCCs matter
Reachable cycle Confirms cycles are handled correctly

Edge Cases

One important edge case is a graph where every node is already reachable from at least one crystal. A buggy implementation might still count SCCs incorrectly if it forgets to exclude reachable components during indegree computation. The implementation explicitly tracks reachable SCCs and skips them entirely when counting answers.

Another critical case is isolated nodes with no incoming or outgoing edges. Each isolated non-crystal node forms its own SCC with indegree zero, so each requires one added rune. The SCC formulation naturally handles this because isolated nodes become singleton SCCs.

Cycles are another common source of bugs. In directed graphs, nodes inside a cycle should be treated as a single unit because reaching one node reaches them all. A node-level greedy approach may overcount required edges. SCC compression prevents this by collapsing entire cycles into single DAG nodes.

A final subtle case involves unreachable SCCs connected together. Suppose SCC A points to SCC B. Only A requires a new rune because once A receives magic, B automatically becomes reachable. The indegree counting step captures exactly this property by counting only zero-indegree unreachable SCCs.