CODEWITHSUNDEEP
pythonalgorithmgraph-algorithm
Wang Liang
Wang Liang

Reputation: 4434

Graphic: Rerouting problem test in python language

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

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.

You are given an array connection consisting of N integers. You are tasked with making a 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.

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

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

Second line contains N integers, ith of which is connectioni.

Constraints

Output Format
An integer representing minimum number of changers required.

Sample Input 0

5
2 3 4 1 5

Sample Output 0

1

Explanation 0

enter image description here

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.

Sample Input 1

4
1 2 3 4

Sample Output 1

3

Explanation 1
enter image description here

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}.

enter image description here

Upvotes: 2

Views: 303

Answers (2)

Ajax1234
Ajax1234

Reputation: 71451

This solution breaks the problem into three steps:

  1. First, all cycles and loops in the input are found.
  2. Next, if any loops exist, the minimum number of steps necessary is returned as the number of loops plus the number of cycles, offset by 1 (all cycles can be connected to a loop, but the connecting loop itself is not counted).
  3. Lastly, if only cycles exist, then the result returned is 1 for a single cycle (since only one rerouting operation is needed to create a terminating loop) or the total number of cycles, offset by 1, if the number of cycles is greater than 1.
from collections import defaultdict
def cycles(n, d, c = [], s = []):
   if n in c or n not in d:
      if n in c:
         yield c
      if (t:=next((i for i in d if i not in s+[n]), None)) is not None:
         yield from cycles(t, d, c = [], s = s+[n])          
   else:
      yield from cycles(d[n], d, c=c+[n], s = s+[n])

def reroute(d):
   c_len, new_d = defaultdict(int), {}
   for a, b in d.items():
      if a != b:
         new_d[a] = b
      else:
         c_len[1] += 1
   if new_d:
      for i in cycles(list(new_d)[0], new_d):
          c_len[len(i)] += 1
   if (loops:=c_len.pop(1, None)) is not None:
      return loops + len(c_len) - 1
   return cl if (cl:=len(c_len)) == 1 else cl - 1

p = ['2 3 4 1 5', '1 2 3 4', '2 3 4 5 5']
r = [reroute(dict(zip(range(1, len(k:=[*map(int, i.split())])+1), k))) for i in p]

Output:

[1, 3, 0]

Upvotes: 2

mcdowella
mcdowella

Reputation: 19601

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.

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.

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.

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.

Upvotes: 2

Related Questions