Minimum Runes to Add to Cast Spell

Problem Description

Ah, the age-old dilemma of casting spells without enough runes! Imagine you’re a wizard trying to impress your friends at a magical gathering, but alas, your spellbook is missing a few runes. The problem at hand is to determine the minimum number of runes you need to add to your collection to cast a spell successfully.

In the world of LeetCode, this translates to a graph problem where you have a set of crystals (your runes) and directed edges (the flow of magic between them). If you don’t have a crystal in a strongly connected component (SCC) of your graph, you might as well be trying to cast a spell with a stick!

Code Solution


class Solution {
 public:
  int minRunesToAdd(int n, vector& crystals, vector& flowFrom,
                    vector& flowTo) {
    vector> graph(n);
    vector> reversedGraph(n);

    for (int i = 0; i < flowFrom.size(); ++i) {
      const int u = flowFrom[i];
      const int v = flowTo[i];
      graph[u].push_back(v);
      reversedGraph[v].push_back(u);
    }

    vector seen(n);
    vector orderStack;
    vector componentIds(n, -1);
    int componentCount = 0;

    for (int i = 0; i < n; ++i)
      if (!seen[i])
        kosaraju(graph, i, seen, orderStack);

    for (int i = n - 1; i >= 0; --i) {
      const int u = orderStack[i];
      if (componentIds[u] == -1)
        identifySCC(reversedGraph, u, componentIds, componentCount++);
    }

    vector hasCrystal(componentCount);
    vector hasInterComponentEdge(componentCount);

    for (const int u : crystals)
      hasCrystal[componentIds[u]] = true;

    for (int i = 0; i < flowFrom.size(); ++i) {
      const int id1 = componentIds[flowFrom[i]];
      const int id2 = componentIds[flowTo[i]];
      if (id1 != id2)
        hasInterComponentEdge[id2] = true;
    }

    int ans = 0;

    for (int i = 0; i < componentCount; ++i)
      if (!hasCrystal[i] && !hasInterComponentEdge[i])
        ++ans;

    return ans;
  }

 private:
  void kosaraju(const vector>& graph, int u, vector& seen,
                vector& orderStack) {
    seen[u] = true;
    for (const int v : graph[u])
      if (!seen[v])
        kosaraju(graph, v, seen, orderStack);
    orderStack.push_back(u);
  }

  void identifySCC(const vector>& reversedGraph, int u,
                   vector& componentIds, int componentId) {
    if (componentIds[u] != -1)
      return;
    componentIds[u] = componentId;
    for (const int v : reversedGraph[u])
      if (componentIds[v] < 0)
        identifySCC(reversedGraph, v, componentIds, componentId);
  }
};

Approach Explanation

The solution employs Kosaraju's Algorithm to identify strongly connected components (SCCs) in a directed graph. The steps are as follows:

Construct the graph and its reversed version.
Perform a depth-first search (DFS) to determine the order of nodes.
Use the reversed graph to identify SCCs.
Track which components contain crystals and which have inter-component edges.
Count the components that lack both crystals and inter-component edges, as these will require additional runes.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(V + E)
Space Complexity	O(V)

Real-World Example

Imagine you're organizing a magical festival where different wizards (components) need to collaborate to create a grand spell. Each wizard has their own set of crystals (runes), but some wizards are isolated and lack the necessary connections (edges) to work together. To ensure the festival is a success, you need to identify how many additional crystals are required for those isolated wizards to join the fun!