python - 图形 : Rerouting problem test in python language

Question

The bounty 将在 42 分钟后过期。这个问题的答案有资格获得 +50 声望奖励。
MERN 希望更多地关注这个问题。







您的公司有 N 服务器。信息通过连接从一台服务器流向另一台服务器。
如果信息从服务器 i 流向服务器 j ，则 connection(i) = j。某些服务器连接(i)= i 是可能的，这意味着信息不会进一步流动。
给定一个由 N 个整数组成的数组连接。您的任务是对连接数组值进行最少数量的更改，以便来自所有服务器的信息可以到达整个网络中的一个服务器，并在那里终止。
如果节点 X 是终端服务器，则 connectioni = X 。
输入格式
第一行包含一个整数 N ，网络中的服务器数。
第二行包含 N 个整数，其中第 i 个是 connectioni。
约束

1 <= N <= 3*105

1 <= connectioni <= N

输出格式
一个整数，表示所需的最少转换器数量。

样本输入 0

5
2 3 4 1 5

样本输出 0

1

解释 0

我们可以选择节点 5 作为我们的终端服务器，并将 4->1 边连接到 4->5。我们修改后的连接数组在只进行 1 更新后就变成了 {2,3,4,5,5}。
样本输入 1

4
1 2 3 4

样本输出 1

3

解释 1

我们可以选择 1 作为我们的终端服务器，并将节点的重置连接到 1 。修改后的连接数组变为 {1,1,1,1} 。

最佳答案

如果您将节点到自身的自链接视为标记而不是真正的链接，那么听起来就像您从一组树开始，其中信息流向树的根部。即使每个节点只有一个传出连接，您仍然可以构建循环，因此问题不是很清楚。
N 个节点的树有 N-1 个链接，所以如果你有 N 个节点形成 k 棵树，你有 N-k 个链接，并且你想生成一个带有 N-1 个链接的树。为此，您可以添加选择其中一棵树，并添加从其他每棵树的根到这棵树的根的 k-1 链接。
您还可以使用链接和节点的计数在开始时检查循环。有 k 个根(通过寻找指向自己的节点找到)和 N 个节点，你应该有 N-k 个链接。如果有循环隐藏在某处，您将拥有多个 N-k 链接。
如果您从一组 k 个不一定是树的组件开始，您仍然需要添加至少 k-1 个新链接来链接它们。您还需要断开除创建循环的标记链接之外的任何链接。因为每个节点只指向一个其他节点，所以唯一的可能性是树和森林，其中看起来像树的根由单个循环连接。您可以通过跟踪节点之间的链接并记住您已经看到哪些节点来找到循环。只有有限数量的节点，所以最终你要么得到一个正确标记的根，要么得到一个你之前在这个过程中见过的节点，你找到了一个循环。您可以通过断开循环中的一个链接，将以循环结尾的森林变成适当的树，该链接的源将成为新的根。

关于python - 图形 : Rerouting problem test in python language，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/62630201/

上一篇：spring - RabbitMQ - 多个消费者如何使用来自单个队列的相同消息？

下一篇：javascript - 公理 : How to run multiple requests one after the other?

相关文章：

python - 如何从 Jinja2 上下文过滤器访问 For 变量

java - 以编程方式将多个 jpeg 图像嵌入到 EXCEL 中？

python - 在代码中处理大数字

c - 进行 URL 匹配和标签提取的有效方法是什么？

graph - 如何合并图中的节点？

algorithm - 我可以将哪些启发式函数用于基于图(非网格)的 A*？

python - 从 matplotlib.pyplot 导入 plt ImportError : No module named 'matplotlib'

python - 来自不同 smtp 服务器的电子邮件 django 服务器错误

c - 如何让下面的递归更快？

algorithm - 如何找到具有价约束的二部图的最大子图？

Answer 1

如果您将节点到自身的自链接视为标记而不是真正的链接，那么听起来就像您从一组树开始，其中信息流向树的根部。即使每个节点只有一个传出连接，您仍然可以构建循环，因此问题不是很清楚。
N 个节点的树有 N-1 个链接，所以如果你有 N 个节点形成 k 棵树，你有 N-k 个链接，并且你想生成一个带有 N-1 个链接的树。为此，您可以添加选择其中一棵树，并添加从其他每棵树的根到这棵树的根的 k-1 链接。
您还可以使用链接和节点的计数在开始时检查循环。有 k 个根(通过寻找指向自己的节点找到)和 N 个节点，你应该有 N-k 个链接。如果有循环隐藏在某处，您将拥有多个 N-k 链接。
如果您从一组 k 个不一定是树的组件开始，您仍然需要添加至少 k-1 个新链接来链接它们。您还需要断开除创建循环的标记链接之外的任何链接。因为每个节点只指向一个其他节点，所以唯一的可能性是树和森林，其中看起来像树的根由单个循环连接。您可以通过跟踪节点之间的链接并记住您已经看到哪些节点来找到循环。只有有限数量的节点，所以最终你要么得到一个正确标记的根，要么得到一个你之前在这个过程中见过的节点，你找到了一个循环。您可以通过断开循环中的一个链接，将以循环结尾的森林变成适当的树，该链接的源将成为新的根。