图:用Python语言重新路由问题测试 [英] Graphic: Rerouting problem test in python language

问题描述

您的公司有 N 个服务器.信息通过连接从一台服务器流向另一台服务器.

Your company has N servers. The information flows from one server to another through a connection.

如果信息从服务器 i 流向服务器 j ，则连接(i)= j.可能存在某些服务器连接(i)= i，这意味着信息不会进一步传播.

If the information flows from server i to server j, then connection(i) = j. It's possible for some server connection(i) = i, meaning information doesn't flow further.

为您提供了一个由N个整数组成的数组连接.您的任务是对连接数组值进行最少的更改，以使来自所有服务器的信息可以到达整个网络中恰好位于其终止位置的一台服务器.

You are given an array connection consisting of N integers. You are tasked with making minimum number of changes to connection array values so that the information from all server can reach at exactly one server in the whole network, where it terminates.

如果节点 X 是终端服务器，则连接 _i = X

If node X is terminal server, then connection_i = X.

输入格式
第一行包含整数 N ，网络中没有服务器.

Input Format
First line contains an integer N, no of servers in the network.

第二行包含N个整数，其中 i ^th 是 connection _i .

Second line contains N integers, i^th of which is connection_i.

约束

• 1< = N< = 3 * 10 ⁵
• 1< =连接 _i < = N

• 1 <= N <= 3*10⁵
• 1 <= connection_i <= N

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

Output Format
An integer representing minimum number of changers required.

样本输入0

5
2 3 4 1 5

示例输出0

1

说明0

我们可以选择节点5作为我们的终端服务器并连接4->1个边到4到5.只需进行 1 更新，我们的修改后的连接数组即变为 {2,3,4,5,5} .

We can choose node 5 as our terminal server and connect 4 -> 1 edge to 4->5. Our modified connection array becomes {2,3,4,5,5} after making just 1 update.

示例输入1

4
1 2 3 4

示例输出1

3

说明1

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

We can select 1 as our terminal server and connect reset of the nodes to 1. The modified connection array becomes {1,1,1,1}.

推荐答案

如果将节点到自身的自我链接视为标记而不是真实链接，那么听起来就像是从一组树开始，信息流向树的根.即使每个节点只有一个传出连接，您仍然可以建立周期，因此问题尚不十分清楚.

If you treat the self-links from a node to itself just as markers and not real links, then it sounds like you start off with a set of trees, where information flows to the root of the tree. Even with just one outgoing connection from each node you can still build cycles, so the problem isn't quite clear on this.

由N个节点组成的树具有N-1个链接，因此，如果您有N个节点形成k个树，则您具有N-k个链接，并且您希望生成具有N-1个链接的单个树.为此，您可以添加选择其中一棵树，并从其他每棵树的根到该树的根添加k-1个链接.

A tree of N nodes has N-1 links, so if you have N nodes forming k trees you have N-k links and you want to produce a single tree with N-1 links. To do this you can add pick one of the trees and add k-1 links from the root of every other tree to the root of this tree.

您还可以使用链接和节点的数量在开始时检查周期.使用k个根(通过查找指向自身的节点找到)和N个节点，您应该具有N-k个链接.如果某个地方藏有周期，那么您将拥有超过N-k个链接.

You can also use the count of links and nodes to check for cycles at the start. With k roots (found by looking for nodes pointing to themselves) and N nodes you should have N-k links. If there are cycles hiding somewhere you will have more than N-k links.

在从一组不一定是树的k个组件开始的情况下，您仍将需要添加至少k-1个新链接以将它们链接起来.除了创建循环的标记链接之外，您还需要断开所有链接.因为每个节点仅指向另一个节点，所以唯一的可能性是树木和森林，其中看起来像树的根部通过单个周期连接在一起.您可以通过跟踪节点之间的链接并记住您已经看到的节点来找到周期.只有有限数量的节点，因此最终您将以正确标记的根结尾，或者最终在此遍之前见过的节点结束，并且发现了一个循环.您可以通过断开循环上的链接之一，使以循环结尾的林变成适当的树，并使该链接的源成为新的根.

In the case where you start off with a set of k components which are not necessarily trees, you are still going to need to add at least k-1 new links to link them up. You also need to break any links other than marker links that create cycles. Because each node points to only one other node the only possibilities are trees and forests where the root of what looks like trees are connected by a single cycle. You could find cycles by following links between nodes and remembering which nodes you have already seen. There are only a finite number of nodes so eventually you end up either with a properly marked root, or a node you have seen before on this pass, and you have found a cycle. You can turn a forest ending with a cycle into a proper tree by breaking one of the links on the cycle, with the source of this link becoming the new root.

这篇关于图:用Python语言重新路由问题测试的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！