3383. Minimum Runes to Add to Cast Spell 🔒

HardDepth-First SearchBreadth-First SearchUnion FindGraphTopological SortArray

Problem Description

Alice has just graduated from wizard school and wants to cast a magic spell to celebrate. The spell contains certain focus points where magic needs to be concentrated, some of which hold magic crystals that serve as the spell's energy source. Focus points are connected through directed runes, allowing magic to flow from one focus point to another.

You are given an integer n which denotes the number of focus points and an array crystals where crystals[i] denotes a focus point containing a magic crystal. Additionally, there are two integer arrays, flowFrom and flowTo, which represent the existing directed runes. The i-th rune allows magic to flow from focus point flowFrom[i] to flowTo[i].

The task is to calculate the minimum number of additional directed runes Alice must add, ensuring each focus point either contains a magic crystal or receives a magic flow from another focus point.

Intuition

The problem involves ensuring that every focus point is either directly powered by a magic crystal or receives magic through the directed rune flow network.

Graph Representation: We represent the focus points as nodes of a directed graph and the runes as edges. flowFrom and flowTo define the direction of these edges.
Reachability Check: We need to check which nodes (focus points) are reachable from any node that has a crystal. First, perform a Breadth-First Search (BFS) from all nodes that contain crystals, marking each visited node.
Finding Unreachable Nodes: After marking all reachable nodes with BFS, the ones left unmarked are those that neither contain a crystal nor receive magic. These are the focus points that need additional runes to connect them either directly or indirectly to a node containing a crystal.
Topological Sort: For each unmarked node, perform a Depth-First Search (DFS) to form a topological order. The reverse order of the topological sort helps identify independent subgraphs (components) that can each be directly linked to crystals using a new directed rune.
Adding Runes: For each such independent subgraph, add a single direct rune from an existing crystal to one of its nodes. This ensures each isolated component becomes connected, either directly or indirectly, to a node with a crystal.

This solution efficiently calculates the minimum connections needed by integrating graph traversal and component detection techniques.

Learn more about Depth-First Search, Breadth-First Search, Union Find, Graph and Topological Sort patterns.

Solution Approach

The approach builds on graph traversal techniques to ensure every focus point can receive magic. Here’s a step-by-step breakdown of the solution:

Graph Construction: We begin by constructing a graph g using the given flowFrom and flowTo arrays. Each pair (a, b) in these arrays forms a directed edge from node a to node b, representing the permissible flow of magic.

g = [[] for _ in range(n)]
for a, b in zip(flowFrom, flowTo):
    g[a].append(b)

Initialize BFS for Reachability: Use a Breadth-First Search (BFS) to mark all focus points that can receive magic from nodes containing crystals. Start the BFS using a queue initialized with the nodes given in the crystals array.

q = deque(crystals)
vis = [0] * n
for x in crystals:
    vis[x] = 1
bfs(q)

Deep Dive with DFS: For nodes that remain unmarked after BFS, perform a Depth-First Search (DFS) to derive a reverse postorder for topological sorting. This DFS traversal helps detect the independent or isolated components of the graph.
```
seq = []
for i in range(n):
    if vis[i] == 0:
        dfs(i)
seq.reverse()
```
The reverse of this order (seq.reverse()) helps identify the minimal points from which the additional runes will ensure connectivity.

Determine Additional Runes: Traverse the topologically sorted nodes. For each node still marked as isolated (vis[i] == 2), initiate a BFS from it to mark all nodes it can lead to as reachable, thus simulating the addition of a rune. Increment a counter ans for each such isolated subcomponent.

ans = 0
for i in seq:
    if vis[i] == 2:
        q = deque([i])
        vis[i] = 1
        bfs(q)
        ans += 1

Return the Result: The counter ans, which accumulates the number of newly added runes, gives the minimal number of runes needed to ensure every focus point is either containing a crystal or connected to a source of magic.

This solution leverages BFS for reachability marking and DFS for sorting to effectively determine the minimal rune additions needed for complete magic flow coverage.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's demonstrate the solution approach using a small example. Consider the following inputs:

n = 6: There are 6 focus points numbered from 0 to 5.
crystals = [0, 1]: Focus points 0 and 1 contain magic crystals.
flowFrom = [0, 1, 4]: Defines the starting points of existing directed runes.
flowTo = [2, 3, 5]: Defines the end points of existing directed runes.

Here's how to solve this:

Graph Construction: We represent the directed runes as edges in a graph g.

g = [
  [2],        # Node 0 has a directed edge to 2
  [3],        # Node 1 has a directed edge to 3
  [],         # Node 2 has no outgoing edges
  [],         # Node 3 has no outgoing edges
  [5],        # Node 4 has a directed edge to 5
  []          # Node 5 has no outgoing edges
]

Initialize BFS for Reachability: Start BFS from the nodes containing crystals (0 and 1).
- Start BFS from node 0: Mark nodes 0 and 2 as reachable.
- Start BFS from node 1: Mark nodes 1 and 3 as reachable.
At this point, focus points 4 and 5 remain unmarked.
Perform DFS for Topological Sorting: Identify isolated or independent components by traversing from unmarked nodes.
- Perform DFS starting from node 4. After traversal, the topological order is [4].
- Node 5 is already reachable due to the rune from node 4.
Determine Additional Runes: Traverse the topologically sorted nodes.
- As node 4 is isolated, we need to connect it with an existing crystal. Assuming we add a new rune from focus point 0 to 4.
- Now, node 5 also becomes reachable, ensuring all nodes receive magic flow.
Return the Result: Since only one new rune was added from focus point 0 to 4, the result is ans = 1.

By following the above steps, we ensured every focus point either contained a magic crystal or received magic through directed runes with a minimal number of additional connections.

Solution Implementation

1from collections import deque
2from typing import List
3
4class Solution:
5    def minRunesToAdd(
6        self, n: int, crystals: List[int], flowFrom: List[int], flowTo: List[int]
7    ) -> int:
8        # Perform a breadth-first search starting from nodes in the queue
9        def bfs(queue: deque):
10            while queue:
11                node = queue.popleft()  # Remove the leftmost element from the deque
12                for neighbor in graph[node]:
13                    if visited[neighbor] == 1:  # Continue if already visited in the current BFS context
14                        continue
15                    visited[neighbor] = 1
16                    queue.append(neighbor)  # Add neighbor to the queue for further exploration
17
18        # Perform a depth-first search to populate the topological sort sequence
19        def dfs(node: int):
20            visited[node] = 2  # Mark the node as visited in DFS context
21            for neighbor in graph[node]:
22                if visited[neighbor] > 0:  # Regular visitation check
23                    continue
24                dfs(neighbor)  # Recursive DFS call
25            sequence.append(node)  # Append the node to the sequence after visiting all neighbors
26
27        # Initialize the graph as an adjacency list
28        graph = [[] for _ in range(n)]
29        # Build the graph from flowFrom to flowTo
30        for start, end in zip(flowFrom, flowTo):
31            graph[start].append(end)
32
33        # Initialize a queue with the crystals
34        queue = deque(crystals)
35        visited = [0] * n  # Visiting state: 0 (not visited), 1 (bfs visited), 2 (dfs visited)
36        for crystal in crystals:
37            visited[crystal] = 1
38        bfs(queue)  # Start BFS from crystals
39
40        # Determine a topological sort sequence
41        sequence = []
42        for i in range(n):
43            if visited[i] == 0:
44                dfs(i)
45      
46        sequence.reverse()  # Reverse sequence to get correct topological order
47        answer = 0
48
49        # Process each node in topological order
50        for node in sequence:
51            if visited[node] == 2:
52                # Start a new BFS from this node and mark it as visited
53                queue = deque([node])
54                visited[node] = 1
55                bfs(queue)
56                answer += 1  # Increment the rune count needed for this source
57
58        return answer
59

1import java.util.*;
2
3class Solution {
4    private int[] visited; // To keep track of visited nodes
5    private List<Integer>[] graph; // Adjacency list to represent the graph
6    private List<Integer> sequence = new ArrayList<>(); // Stores the reversed post-order of nodes
7
8    public int minRunesToAdd(int n, int[] crystals, int[] flowFrom, int[] flowTo) {
9        // Initialize the graph with an empty list for each node
10        graph = new List[n];
11        Arrays.setAll(graph, i -> new ArrayList<>());
12      
13        // Build the graph using the flowFrom and flowTo arrays
14        for (int i = 0; i < flowFrom.length; ++i) {
15            graph[flowFrom[i]].add(flowTo[i]);
16        }
17
18        Deque<Integer> queue = new ArrayDeque<>();
19        visited = new int[n];
20      
21        // Mark the crystal nodes as visited
22        for (int crystal : crystals) {
23            visited[crystal] = 1;
24            queue.offer(crystal);
25        }
26      
27        // Perform BFS starting from all crystal nodes
28        breadthFirstSearch(queue);
29      
30        // Perform DFS on unvisited nodes to fill sequence in post-order
31        for (int i = 0; i < n; ++i) {
32            if (visited[i] == 0) {
33                depthFirstSearch(i);
34            }
35        }
36
37        int additionalRunes = 0;
38      
39        // Reverse post-order processing to find the minimal set of runes needed
40        for (int i = sequence.size() - 1; i >= 0; --i) {
41            int node = sequence.get(i);
42            if (visited[node] == 2) { // Node that requires a rune
43                visited[node] = 1;
44                queue.clear();
45                queue.offer(node);
46                breadthFirstSearch(queue);
47                ++additionalRunes;
48            }
49        }
50      
51        return additionalRunes;
52    }
53
54    private void breadthFirstSearch(Deque<Integer> queue) {
55        while (!queue.isEmpty()) {
56            int currentNode = queue.poll();
57            for (int neighbor : graph[currentNode]) {
58                if (visited[neighbor] == 1) {
59                    continue;
60                }
61                visited[neighbor] = 1;
62                queue.offer(neighbor);
63            }
64        }
65    }
66
67    private void depthFirstSearch(int node) {
68        visited[node] = 2;
69        for (int neighbor : graph[node]) {
70            if (visited[neighbor] > 0) {
71                continue;
72            }
73            depthFirstSearch(neighbor);
74        }
75        sequence.add(node);
76    }
77}
78

1#include <vector>
2#include <deque>
3
4using namespace std;
5
6class Solution {
7public:
8    vector<int> visited;           // To mark visited nodes and their state
9    vector<vector<int>> graph;     // Adjacency list representation of the graph
10    vector<int> sequence;          // Stores the order of nodes determined by DFS
11
12    // Function to calculate the minimum number of runes to add
13    int minRunesToAdd(int n, vector<int>& crystals, vector<int>& flowFrom, vector<int>& flowTo) {
14        graph.resize(n);  // Initialize graph with 'n' nodes
15        // Fill the adjacency list
16        for (int i = 0; i < flowFrom.size(); ++i) {
17            graph[flowFrom[i]].push_back(flowTo[i]);
18        }
19
20        deque<int> queue;   // Queue for BFS
21        visited.resize(n, 0);  // Initialize visited array with 0
22
23        // Marking initial crystal nodes as visited and adding them to the queue
24        for (int crystal : crystals) {
25            visited[crystal] = 1;
26            queue.push_back(crystal);
27        }
28        bfs(queue);  // Perform BFS to mark reachable nodes
29
30        // Perform DFS for unvisited nodes to detect connected components
31        for (int i = 0; i < n; ++i) {
32            if (visited[i] == 0) {
33                dfs(i);
34            }
35        }
36
37        int ans = 0;  // Variable to store the number of runes to add
38
39        // Traverse the sequence in reverse order to determine additional runes needed
40        for (int i = sequence.size() - 1; i >= 0; --i) {
41            int node = sequence[i];
42            if (visited[node] == 2) {
43                visited[node] = 1;
44                queue.clear();
45                queue.push_back(node);
46                bfs(queue);
47                ++ans;  // Increment the number of runes to add
48            }
49        }
50        return ans;
51    }
52
53private:
54    // BFS function to traverse the graph from initial crystal nodes
55    void bfs(deque<int>& queue) {
56        while (!queue.empty()) {
57            int current = queue.front();
58            queue.pop_front();
59            // Traverse all connected nodes from the current node
60            for (int neighbor : graph[current]) {
61                if (visited[neighbor] == 1) {
62                    continue;  // Skip already visited nodes
63                }
64                visited[neighbor] = 1;
65                queue.push_back(neighbor);
66            }
67        }
68    }
69
70    // DFS function to explore graph and record sequence of nodes
71    void dfs(int node) {
72        visited[node] = 2;  // Mark current node as visited with a special state
73        for (int neighbor : graph[node]) {
74            if (visited[neighbor] > 0) {
75                continue;  // Skip already visited nodes
76            }
77            dfs(neighbor);  // Recursive DFS call
78        }
79        sequence.push_back(node);  // Add current node to sequence after DFS completes
80    }
81};
82

1function minRunesToAdd(
2    n: number,
3    crystals: number[],
4    flowFrom: number[],
5    flowTo: number[],
6): number {
7
8    // Create an adjacency list to represent the graph
9    const graph: number[][] = Array.from({ length: n }, () => []);
10    for (let i = 0; i < flowFrom.length; i++) {
11        const from = flowFrom[i];
12        const to = flowTo[i];
13        graph[from].push(to);
14    }
15
16    // vis array to track the state of each node (0: unvisited, 1: reachable, 2: processed)
17    const vis: number[] = Array(n).fill(0);
18    for (const crystalNode of crystals) {
19        vis[crystalNode] = 1;  // Mark crystal nodes as reachable
20    }
21
22    // Breadth-first search to mark all nodes reachable from initial crystal nodes
23    const bfs = (queue: number[]) => {
24        while (queue.length > 0) {
25            const current = queue.shift()!;
26            for (const neighbor of graph[current]) {
27                if (vis[neighbor] === 1) continue;  // Skip if already marked reachable
28                vis[neighbor] = 1;  // Mark neighbor as reachable
29                queue.push(neighbor);
30            }
31        }
32    };
33
34    // Depth-first search to order nodes in the sequence for further processing
35    const sequence: number[] = [];
36    const dfs = (node: number) => {
37        vis[node] = 2;  // Mark node as processed
38        for (const neighbor of graph[node]) {
39            if (vis[neighbor] > 0) continue;  // Skip if already visited/processed
40            dfs(neighbor);
41        }
42        sequence.push(node);  // Add node to sequence after processing its neighbors
43    };
44
45    bfs(crystals);
46
47    // Perform DFS to find all nodes and order them for a later reachability check
48    for (let i = 0; i < n; i++) {
49        if (vis[i] === 0) {  // Unvisited nodes
50            dfs(i);
51        }
52    }
53
54    sequence.reverse();  // Reverse sequence to process nodes in correct order
55
56    let runesNeeded = 0;
57    for (const node of sequence) {
58        if (vis[node] === 2) {  // If node is marked as processed, needs rerun of BFS
59            bfs([node]);
60            vis[node] = 1;  // Mark as reachable
61            runesNeeded++;  // Increment runes needed
62        }
63    }
64
65    return runesNeeded;
66}
67

Time and Space Complexity

The algorithm involves several key steps that contribute to the computational complexity. Here's a breakdown:

Graph Representation:
- Time complexity for building the adjacency list g: O(E), where E is the number of edges (equal to the length of flowFrom and flowTo).
Breadth-First Search (BFS):
- The initial BFS traversal is used to mark all reachable nodes from the given crystals. The time complexity for this is O(V + E), where V is the number of vertices (equal to n).
- Space complexity for BFS: O(V) for the vis list and the queue q.
Depth-First Search (DFS):
- DFS is used to find a valid topological sort of the graph. The time complexity for this is O(V + E).
- Space complexity for DFS: O(V) for the vis list, seq list, and recursion stack.
Reversing the Sequence:
- Time complexity for reversing seq: O(V).
Final BFS and Counting:
- For each node in the reverse topological order, a BFS is applied to find and mark strongly connected components. This also takes O(V + E) in total.
- The final complexity of counting the number of BFS invocations results in O(V).

Combining these, since each node and edge is processed a constant number of times, the overall time complexity is O(V + E). The space complexity is primarily determined by the graph storage and visit tracking, thus it's O(V).

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function call

Determine return value

Determine how many recursive calls will be made

Tracing the recursive calls