PROBLEM LINK:
Author: Hasan Jaddouh
Tester: Misha Chorniy
Editorialist: Pushkar Mishra
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Graphs, Articulation points/edges
PROBLEM:
Given a graph with N nodes and M edges. We have to tell whether it is possible to augment the graph in a way such that every pair of nodes has at least two mutually disjoint paths between them. The only modification that can be done is addition of one edge.
EXPLANATION:
The prroblem asks us to add one and only one edge such that the graph becomes âgoodâ, i.e., for every pair of nodes u and v, there are at least two mutually disjoint paths to go from u to v or the other way.
Let us first try to observe some properties of a âgoodâ graph. A very basic but very powerful observation is that since in a good graph there are two mutually disjoint paths between every pair of nodes u and v, this means that u and v are part of a closed loop. In other words, u and v are a part of at least one common cycle.
This gives us a very important lead. We need to focus on cycles. But what about them? Here comes another very important observation. If an edge is a part of a cycle then the two endpoints of that edge, say x and y, will always form âgoodâ pairs with all other nodes z of the graph unless the path or edge between z and x (similar for z and y) is âcriticalâ. By critical we mean that breaking that edge or breaking any edge of the path will disconnect the graph.
This observation leads us to concentrate on specific types of edges. To be more specific, we need to think about those edges which if broken will disconnect the path. Such edges are called Bridges or Articulation Edges. There is a very special property about them that they donât belong to any cycles. So the first step in our formal algorithm is to find all the bridges. This can be done with a single pass of a depth-first search, using Tarjanâs Bridge Finding Algorithm. In this part, we need to take care of the parallel edges, i.e., multiple edges between two nodes. This is because if parallel edges between u and v exist then any of those parallel edges canât be bridges. For checking this, we can store the edges of a graph in a map paired with their number of occurrences. If an edge occurs more than once, it canât be a bridge. Care also needs to be taken that the set of edges that we get as bridges has unique entries; any repeats should be removed.
Once we have found the bridges, we need to think of a way of putting them in a cycle. This is because bridges are those edges that always have to be present in the path from a node on one side of the bridge to a node on the other side of it. This is against our desired property of âgoodnessâ. So to eliminate that, if we can make all the bridges part of cycles within the graph, then they will no more remain bridges. The constraint is that we can only add one edge to our graph. So this means, by the addition one edge, we should be able to get all our bridges, wherever they are in the graph, into one cycle.
How do we do this? To be able to belong to one cycle, the bridges must fall in one line. By one line, we mean that if we start traversing from a bridge at least one of whose endpoints is not shared with any any other bridge (such a bridge will exist; otherwise all bridges will already be forming a cycle and hence not be bridges at all), then we should be able to visit every other bridge in the graph by taking one and only one edge from each node that we visit during traversal.
Such a traversal is just a constrained DFS. To find the start point of the traversal, we simply count the degree of each of the endpoints of bridges when only considering the bridges (no other edges). With the help of some if-else constructs, we can do such a traversal and check at the end of it whether all nodes that belong to bridges got traversed or not. If not, then output NO else YES.
We have used map in our algorithm to take care of parallel edges. This makes our algorithm \mathcal{O}(N\log N) in the worst case. However, structures like hashmaps can do away with the extra \log N factor. However, \mathcal{O}(N\log N) is sufficient for getting a solution accepted.
Please see editorialistâs/setterâs program for implementation details.
COMPLEXITY:
\mathcal{O}(N\log N)