| comments | difficulty | edit_url | tags | ||||||
|---|---|---|---|---|---|---|---|---|---|
true |
困难 |
|
Alice 刚刚从巫师学校毕业，并且希望施展一个魔法咒语来庆祝。魔法咒语包含某些需要集中魔力的焦点，其中一些焦点含有作为咒语能量源的魔法水晶。焦点可以通过 有向符文 进行连接，这些符文将魔力流从一个焦点传输到另一个焦点。
给定一个整数 n 表示焦点的数量，以及一个整数数组 crystals，其中 crystals[i] 表示有魔法水晶的焦点。同时给定两个整数数组 flowFrom 和 flowTo，表示存在的 有向符文。第 ith 个符文允许魔力流从焦点 flowFrom[i] 传输到焦点 flowTo[i]。
你需要找到 Alice 必须添加到她的咒语中的定向符文数量，使得每个焦点要么：
- 包含 一个魔法水晶。
- 从其它焦点 接收 魔力流。
返回她所需要添加的 最少 有向符文数量。
示例 1：
输入：n = 6, crystals = [0], flowFrom = [0,1,2,3], flowTo = [1,2,3,0]
输出：2
解释：
添加两个有向符文：
- 从焦点 0 到焦点 4。
- 从焦点 0 到焦点 5。
示例 2：
输入：n = 7, crystals = [3,5], flowFrom = [0,1,2,3,5], flowTo = [1,2,0,4,6]
输出：1
解释：
添加从焦点 4 到焦点 2 的有向符文。
提示：
2 <= n <= 1051 <= crystals.length <= n0 <= crystals[i] <= n - 11 <= flowFrom.length == flowTo.length <= min(2 * 105, (n * (n - 1)) / 2)0 <= flowFrom[i], flowTo[i] <= n - 1flowFrom[i] != flowTo[i]- 所有的有向符文 互不相同。
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 ansclass 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);
}
}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);
}
};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
}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;
}