You have been hired by the university to manage the wireless network across campus. The network is set up as follows: there is one modem and many routers, which need to be connected together by cables. A router can only function if there is some path of cables (possibly through other routers) that connects it to the modem. Your job is to establish this network and keep all the routers functioning properly. There are many cables already in place between the routers, but they are old and malfunctioning. It is not within your budget to replace them with new cables, and so you will need to manage this network by repairing faulty cables. (Assume that it is possible to connect the whole network with these faulty cables, and that all the cables can carry data in both directions.) You think back to what you learned in 330, and remember that you can use DFS to find a tree that connects every router to the modem. So, you run DFS from the modem (faulty cables are edges and the routers/modem are vertices) and repair all the tree edges of the DFS tree. Good job! We will denote this tree of now functioning cables as T. However, since these cables are old and prone to failure, one of them might stop working at any time! Therefore, the university wants to know how many malfunctioning cables can potentially replace a repaired cable in case it permanently fails. To formalize this, let e be some repaired cable. If this cable were removed, T would be split into two connected components. The modem would be in one of these components, and all the routers in the other component would no longer be connected to the modem! However, there may be other malfunctioning cables that connect these two components, therefore, repairing one of those cables will reconnect the network. The university wants to know how many such malfunctioning cables are there for each repaired cable Give an algorithm that computes all these counts (one for each edge in T) in O(m) time, where m is the total number of cables, both repaired and malfunctioning. You may assume that for a pair of routers/modem u and v, you can determine if u is an ancestor of v in T in O (1) time Would your algorithm work if tree T were any spanning tree of the network (instead of being a DFS tree)? You have been hired by the university to manage the wireless network across campus. The network is set up as follows: there is one modem and many routers, which need to be connected together by cables. A router can only function if there is some path of cables (possibly through other routers) that connects it to the modem. Your job is to establish this network and keep all the routers functioning properly. There are many cables already in place between the routers, but they are old and malfunctioning. It is not within your budget to replace them with new cables, and so you will need to manage this network by repairing faulty cables. (Assume that it is possible to connect the whole network with these faulty cables, and that all the cables can carry data in both directions.) You think back to what you learned in 330, and remember that you can use DFS to find a tree that connects every router to the modem. So, you run DFS from the modem (faulty cables are edges and the routers/modem are vertices) and repair all the tree edges of the DFS tree. Good job! We will denote this tree of now functioning cables as T. However, since these cables are old and prone to failure, one of them might stop working at any time! Therefore, the university wants to know how many malfunctioning cables can potentially replace a repaired cable in case it permanently fails. To formalize this, let e be some repaired cable. If this cable were removed, T would be split into two connected components. The modem would be in one of these components, and all the routers in the other component would no longer be connected to the modem! However, there may be other malfunctioning cables that connect these two components, therefore, repairing one of those cables will reconnect the network. The university wants to know how many such malfunctioning cables are there for each repaired cable Give an algorithm that computes all these counts (one for each edge in T) in O(m) time, where m is the total number of cables, both repaired and malfunctioning. You may assume that for a pair of routers/modem u and v, you can determine if u is an ancestor of v in T in O (1) time Would your algorithm work if tree T were any spanning tree of the network (instead of being a DFS tree)
