MADE EASY TEST SERIES

Question

A network of n computers is such that we have m pairs of computers connected using full duplex wired links: a full duplex link is a direct two-way wired connection between two computers. The wired connectivity of a computer is the number of computers it can talk to via any sequence of wired links. What is the efficient time complexity to find a largest subset of existing wired links that could be removed without changing any computer’s wired connectivity.

I wasn’t able to think how to solve this question.HELP.

Comments

A graph search while marking visited edges would help.

Answer 1

Here, imagine the entire network as a graph, computers as nodes and links as edges. They are connected by wires ie it forms connected component.

So now, you have to find the time complexity of the largest connected component whose removal may not affect the connectivity of the graph.

The largest connected component can be found by DFS traversal on the graph whose time complexity is  O(V+E) using adjacency list representation.

So, using this you can find out the time complexity.