Minimum runes to add to cast spell

Array Depth-First Search Breadth-First Search Union-Find Graph Theory Topological Sort

44.6% acceptance

Mar 31, 2026

Alice has just graduated from wizard school, and wishes to cast a magic spell to celebrate. The magic spell contains certain focus points where magic needs to be concentrated, and some of these focus points contain magic crystals which serve as the spell's energy source. Focus points can be linked through directed runes, which channel magic flow from one focus point to another. You are given a integer n denoting the number of focus points and an array of integers crystals where crystals[i] indicates a focus point which holds a magic crystal. You are also given two integer arrays flowFrom and flowTo, which represent the existing directed runes. The ith rune allows magic to freely flow from focus point flowFrom[i] to focus point flowTo[i]. You need to find the number of directed runes Alice must add to her spell, such that each focus point either: Contains a magic crystal. Receives magic flow from another focus point. Return the minimum number of directed runes that she should add.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_runes_to_add(n: i32, crystals: Vec<i32>, flow_from: Vec<i32>, flow_to: Vec<i32>) -> i32 {
    let n = n as usize;
    // Build reverse graph and find which nodes can reach a crystal
    // Actually: we need every node to either have a crystal or receive flow.
    // "Receive flow" means there's a directed path from some crystal to that node.
    // We need to add minimum edges to make every node reachable from some crystal.
    // 
    // Reverse the graph. A node is "covered" if it can reach a crystal in the reverse graph.
    // Equivalently, in the original graph, a crystal can reach that node.
    //
    // Strategy: Find SCCs. Condense the graph. Count source SCCs (in-degree 0 in condensed DAG)
    // that don't contain a crystal. Each such SCC needs one incoming rune.
    
    let mut adj = vec![vec![]; n];
    let mut radj = vec![vec![]; n];
    for i in 0..flow_from.len() {
      let u = flow_from[i] as usize;
      let v = flow_to[i] as usize;
      adj[u].push(v);
      radj[v].push(u);
    }
    
    // Kosaraju's SCC
    let mut order = Vec::with_capacity(n);
    let mut visited = vec![false; n];
    
    fn dfs1(u: usize, adj: &[Vec<usize>], visited: &mut [bool], order: &mut Vec<usize>) {
      visited[u] = true;
      for &v in &adj[u] {
        if !visited[v] {
          dfs1(v, adj, visited, order);
        }
      }
      order.push(u);
    }
    
    for i in 0..n {
      if !visited[i] {
        dfs1(i, &adj, &mut visited, &mut order);
      }
    }
    
    let mut comp = vec![0usize; n];
    let mut num_comp = 0;
    visited = vec![false; n];
    
    fn dfs2(u: usize, radj: &[Vec<usize>], visited: &mut [bool], comp: &mut [usize], c: usize) {
      visited[u] = true;
      comp[u] = c;
      for &v in &radj[u] {
        if !visited[v] {
          dfs2(v, radj, visited, comp, c);
        }
      }
    }
    
    for &u in order.iter().rev() {
      if !visited[u] {
        dfs2(u, &radj, &mut visited, &mut comp, num_comp);
        num_comp += 1;
      }
    }
    
    // Check which components have crystals
    let mut has_crystal = vec![false; num_comp];
    for &c in &crystals {
      has_crystal[comp[c as usize]] = true;
    }
    
    // Check in-degree of each component in condensed DAG
    let mut in_degree = vec![0; num_comp];
    for u in 0..n {
      for &v in &adj[u] {
        if comp[u] != comp[v] {
          in_degree[comp[v]] += 1;
        }
      }
    }
    
    // Count source SCCs without crystal
    let mut ans = 0;
    for c in 0..num_comp {
      if in_degree[c] == 0 && !has_crystal[c] {
        ans += 1;
      }
    }
    ans
  }
}