Minimum Runes to Add to Cast Spell Solution in Python

Explore Other Solutions

Problem Description

So, you want to cast a spell, huh? But wait! You need runes, and not just any runes—minimum runes! Imagine you’re at a magical party, and everyone is casting spells left and right. You, on the other hand, are stuck in the corner, trying to figure out how many runes you need to join the fun. The problem is, you have a bunch of crystals (which are like your magical friends) and a network of spells (the connections between them). Your task is to figure out how many more runes you need to add to be able to cast your spell without being left out.

In technical terms, given a directed graph where nodes represent crystals and edges represent the flow of magic between them, you need to find the minimum number of additional runes required to ensure that you can cast your spell from any crystal.

Code Solution


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

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

        seen = set()
        orderStack = []
        componentIds = [-1] * n
        componentCount = 0

        for i in range(n):
            if i not in seen:
                self._kosaraju(graph, i, seen, orderStack)

        while orderStack:
            u = orderStack.pop()
            if componentIds[u] == -1:
                self._identifySCC(reversedGraph, u, componentIds, componentCount)
                componentCount += 1

        hasCrystal = [False] * componentCount
        hasInterComponentEdge = [False] * componentCount

        for u in crystals:
            hasCrystal[componentIds[u]] = True

        for u, v in zip(flowFrom, flowTo):
            id1 = componentIds[u]
            id2 = componentIds[v]
            if id1 != id2:
                hasInterComponentEdge[id2] = True

        return sum(not hasCrystal[i] and not hasInterComponentEdge[i]
                   for i in range(componentCount))

    def _kosaraju(
        self,
        graph: list[list[int]],
        u: int,
        seen: set[int],
        orderStack: list
    ) -> None:
        seen.add(u)
        for v in graph[u]:
            if v not in seen:
                self._kosaraju(graph, v, seen, orderStack)
        orderStack.append(u)

    def _identifySCC(
        self,
        reversedGraph: list[list[int]],
        u: int,
        componentIds: list[int],
        componentId: int
    ) -> None:
        if componentIds[u] != -1:
            return
        componentIds[u] = componentId
        for v in reversedGraph[u]:
            if componentIds[v] == -1:
                self._identifySCC(reversedGraph, v, componentIds, componentId)

Approach Explanation

The solution employs Kosaraju’s algorithm to identify Strongly Connected Components (SCCs) in the directed graph. The algorithm works in two main passes:

First Pass: Perform a depth-first search (DFS) on the original graph to determine the order of nodes based on their finishing times.
Second Pass: Reverse the graph and perform DFS again, this time to identify the SCCs based on the order obtained from the first pass.

After identifying the SCCs, the algorithm checks which components contain crystals and whether there are inter-component edges. Finally, it counts the number of components that lack crystals and inter-component edges, which gives the minimum number of runes needed.

Time and Space Complexity

Time Complexity: O(V + E), where V is the number of vertices (crystals) and E is the number of edges (flows). This is because each vertex and edge is processed a constant number of times.
Space Complexity: O(V + E) for storing the graph and the reversed graph.

Real-World Example

Imagine you’re at a magical convention where different booths represent different crystals. Each booth has a unique spell (flow) that connects it to another booth. Some booths have magical crystals (your friends), while others are just empty. To ensure you can cast your spell from any booth, you need to figure out how many more booths (runes) you need to set up to connect all the booths with crystals. The solution helps you determine that number, ensuring you can join the magical fun!