Skip to content

3383. Minimum Runes to Add to Cast Spell πŸ”’

Description

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.

 

Example 1:

Input: n = 6, crystals = [0], flowFrom = [0,1,2,3], flowTo = [1,2,3,0]

Output: 2

Explanation: 

Add two directed runes:

  • From focus point 0 to focus point 4.
  • From focus point 0 to focus point 5.

Example 2:

Input: n = 7, crystals = [3,5], flowFrom = [0,1,2,3,5], flowTo = [1,2,0,4,6]

Output: 1

Explanation: 

Add a directed rune from focus point 4 to focus point 2.

 

Constraints:

  • 2 <= n <= 105
  • 1 <= crystals.length <= n
  • 0 <= crystals[i] <= n - 1
  • 1 <= flowFrom.length == flowTo.length <= min(2 * 105, (n * (n - 1)) / 2)
  • 0 <= flowFrom[i], flowTo[i] <= n - 1
  • flowFrom[i] != flowTo[i]
  • All pre-existing directed runes are distinct.

Solutions

Solution 1

 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
class Solution:
    def minRunesToAdd(
        self, n: int, crystals: List[int], flowFrom: List[int], flowTo: List[int]
    ) -> int:
        def bfs(q: Deque[int]):
            while q:
                a = q.popleft()
                for b in g[a]:
                    if vis[b] == 1:
                        continue
                    vis[b] = 1
                    q.append(b)

        def dfs(a: int):
            vis[a] = 2
            for b in g[a]:
                if vis[b] > 0:
                    continue
                dfs(b)
            seq.append(a)

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

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

        seq = []
        for i in range(n):
            if vis[i] == 0:
                dfs(i)
        seq.reverse()
        ans = 0
        for i in seq:
            if vis[i] == 2:
                q = deque([i])
                vis[i] = 1
                bfs(q)
                ans += 1
        return ans

 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
class Solution {
    private int[] vis;
    private List<Integer>[] g;
    private List<Integer> seq = new ArrayList<>();

    public int minRunesToAdd(int n, int[] crystals, int[] flowFrom, int[] flowTo) {
        g = new List[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int i = 0; i < flowFrom.length; ++i) {
            g[flowFrom[i]].add(flowTo[i]);
        }
        Deque<Integer> q = new ArrayDeque<>();
        vis = new int[n];
        for (int i : crystals) {
            vis[i] = 1;
            q.offer(i);
        }
        bfs(q);
        for (int i = 0; i < n; ++i) {
            if (vis[i] == 0) {
                dfs(i);
            }
        }
        int ans = 0;
        for (int i = seq.size() - 1; i >= 0; --i) {
            int a = seq.get(i);
            if (vis[a] == 2) {
                vis[a] = 1;
                q.clear();
                q.offer(a);
                bfs(q);
                ++ans;
            }
        }
        return ans;
    }

    private void bfs(Deque<Integer> q) {
        while (!q.isEmpty()) {
            int a = q.poll();
            for (int b : g[a]) {
                if (vis[b] == 1) {
                    continue;
                }
                vis[b] = 1;
                q.offer(b);
            }
        }
    }

    private void dfs(int a) {
        vis[a] = 2;
        for (int b : g[a]) {
            if (vis[b] > 0) {
                continue;
            }
            dfs(b);
        }
        seq.add(a);
    }
}

 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
class Solution {
public:
    vector<int> vis;
    vector<vector<int>> g;
    vector<int> seq;

    int minRunesToAdd(int n, vector<int>& crystals, vector<int>& flowFrom, vector<int>& flowTo) {
        g.resize(n);
        for (int i = 0; i < flowFrom.size(); ++i) {
            g[flowFrom[i]].push_back(flowTo[i]);
        }

        deque<int> q;
        vis.resize(n, 0);
        for (int i : crystals) {
            vis[i] = 1;
            q.push_back(i);
        }
        bfs(q);

        for (int i = 0; i < n; ++i) {
            if (vis[i] == 0) {
                dfs(i);
            }
        }

        int ans = 0;
        for (int i = seq.size() - 1; i >= 0; --i) {
            int a = seq[i];
            if (vis[a] == 2) {
                vis[a] = 1;
                q.clear();
                q.push_back(a);
                bfs(q);
                ++ans;
            }
        }
        return ans;
    }

private:
    void bfs(deque<int>& q) {
        while (!q.empty()) {
            int a = q.front();
            q.pop_front();
            for (int b : g[a]) {
                if (vis[b] == 1) {
                    continue;
                }
                vis[b] = 1;
                q.push_back(b);
            }
        }
    }

    void dfs(int a) {
        vis[a] = 2;
        for (int b : g[a]) {
            if (vis[b] > 0) {
                continue;
            }
            dfs(b);
        }
        seq.push_back(a);
    }
};

 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
func minRunesToAdd(n int, crystals []int, flowFrom []int, flowTo []int) (ans int) {
    g := make([][]int, n)
    for i := 0; i < len(flowFrom); i++ {
        a, b := flowFrom[i], flowTo[i]
        g[a] = append(g[a], b)
    }

    vis := make([]int, n)
    for _, x := range crystals {
        vis[x] = 1
    }

    bfs := func(q []int) {
        for len(q) > 0 {
            a := q[0]
            q = q[1:]
            for _, b := range g[a] {
                if vis[b] == 1 {
                    continue
                }
                vis[b] = 1
                q = append(q, b)
            }
        }
    }

    seq := []int{}
    var dfs func(a int)
    dfs = func(a int) {
        vis[a] = 2
        for _, b := range g[a] {
            if vis[b] > 0 {
                continue
            }
            dfs(b)
        }
        seq = append(seq, a)
    }

    q := crystals
    bfs(q)

    for i := 0; i < n; i++ {
        if vis[i] == 0 {
            dfs(i)
        }
    }

    for i, j := 0, len(seq)-1; i < j; i, j = i+1, j-1 {
        seq[i], seq[j] = seq[j], seq[i]
    }
    for _, i := range seq {
        if vis[i] == 2 {
            q = []int{i}
            vis[i] = 1
            bfs(q)
            ans++
        }
    }
    return
}

 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
function minRunesToAdd(
    n: number,
    crystals: number[],
    flowFrom: number[],
    flowTo: number[],
): number {
    const g: number[][] = Array.from({ length: n }, () => []);
    for (let i = 0; i < flowFrom.length; i++) {
        const a = flowFrom[i],
            b = flowTo[i];
        g[a].push(b);
    }

    const vis: number[] = Array(n).fill(0);
    for (const x of crystals) {
        vis[x] = 1;
    }

    const bfs = (q: number[]) => {
        while (q.length > 0) {
            const a = q.shift()!;
            for (const b of g[a]) {
                if (vis[b] === 1) continue;
                vis[b] = 1;
                q.push(b);
            }
        }
    };

    const seq: number[] = [];
    const dfs = (a: number) => {
        vis[a] = 2;
        for (const b of g[a]) {
            if (vis[b] > 0) continue;
            dfs(b);
        }
        seq.push(a);
    };

    bfs(crystals);

    for (let i = 0; i < n; i++) {
        if (vis[i] === 0) {
            dfs(i);
        }
    }

    seq.reverse();

    let ans = 0;
    for (const i of seq) {
        if (vis[i] === 2) {
            bfs([i]);
            vis[i] = 1;
            ans++;
        }
    }

    return ans;
}

Comments