Skip to content

3383. Minimum Runes to Add to Cast Spell

  • Time: O(∣V∣+∣E∣)O(|V| + |E|)
  • Space: O(∣V∣+∣E∣)O(|V| + |E|)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class Solution {
 public:
  int minRunesToAdd(int n, vector<int>& crystals, vector<int>& flowFrom,
                    vector<int>& flowTo) {
    vector<vector<int>> graph(n);
    vector<vector<int>> 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);
    }

    // Identify Strongly Connected Components (SCC) using Kosaraju's Algorithm
    vector<bool> seen(n);
    vector<int> orderStack;
    vector<int> 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++);
    }

    // Track crystal-containing components and inter-component edges.
    vector<bool> hasCrystal(componentCount);
    vector<bool> 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)  // Edge is inter-component.
        hasInterComponentEdge[id2] = true;
    }

    // Count components requiring additional runes.
    int ans = 0;

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

    return ans;
  }

 private:
  // Creates a topological order stack using Kosaraju's Algorithm.
  void kosaraju(const vector<vector<int>>& graph, int u, vector<bool>& seen,
                vector<int>& orderStack) {
    seen[u] = true;
    for (const int v : graph[u])
      if (!seen[v])
        kosaraju(graph, v, seen, orderStack);
    orderStack.push_back(u);
  }

  // Assigns component IDs during SCC identification in the second DFS.
  void identifySCC(const vector<vector<int>>& reversedGraph, int u,
                   vector<int>& 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);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class Solution {
  public int minRunesToAdd(int n, int[] crystals, int[] flowFrom, int[] flowTo) {
    List<Integer>[] graph = new ArrayList[n];
    List<Integer>[] reversedGraph = new ArrayList[n];

    for (int i = 0; i < n; ++i) {
      graph[i] = new ArrayList<>();
      reversedGraph[i] = new ArrayList<>();
    }

    for (int i = 0; i < flowFrom.length; ++i) {
      final int u = flowFrom[i];
      final int v = flowTo[i];
      graph[u].add(v);
      reversedGraph[v].add(u);
    }

    // Identify Strongly Connected Components (SCC) using Kosaraju's Algorithm.
    boolean[] seen = new boolean[n];
    List<Integer> orderStack = new ArrayList<>();
    int[] componentIds = new int[n];
    int componentCount = 0;

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

    Arrays.fill(componentIds, -1);

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

    // Track crystal-containing components and inter-component edges.
    boolean[] hasCrystal = new boolean[componentCount];
    boolean[] hasInterComponentEdge = new boolean[componentCount];

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

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

    // Count components requiring additional runes
    int ans = 0;

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

    return ans;
  }

  // Creates a topological order stack using Kosaraju's Algorithm.
  private void kosaraju(List<Integer>[] graph, int u, boolean[] seen, List<Integer> orderStack) {
    seen[u] = true;
    for (final int v : graph[u])
      if (!seen[v])
        kosaraju(graph, v, seen, orderStack);
    orderStack.add(u);
  }

  // Assigns component IDs during SCC identification in the second DFS.
  private void identifySCC(List<Integer>[] reversedGraph, int u, int[] componentIds,
                           int componentId) {
    if (componentIds[u] != -1)
      return;
    componentIds[u] = componentId;
    for (final int v : reversedGraph[u])
      if (componentIds[v] == -1)
        identifySCC(reversedGraph, v, componentIds, componentId);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
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)

    # Identify Strongly Connected Components (SCC) using Kosaraju's Algorithm.
    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

    # Track crystal-containing components and inter-component edges.
    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:  # Edge is inter-component.
        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:
    """Creates a topological order stack using Kosaraju's Algorithm."""
    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:
    """Assigns component IDs during SCC identification in the second DFS."""
    if componentIds[u] != -1:
      return
    componentIds[u] = componentId
    for v in reversedGraph[u]:
      if componentIds[v] == -1:
        self._identifySCC(reversedGraph, v, componentIds, componentId)
Was this page helpful?