CHEFLAND - Editorial

bridges
chefland
cook71
editorial
graph
medium-hard

#1

PROBLEM LINK:

Practice
Contest

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)

SAMPLE SOLUTIONS:

Author
Tester


#2

You can solve in O(N) by maintaining an edge-list instead of a hash-map to handle parallel edges.


#3

Why is this problem in the « Easy » part of the practice website?


#4

For the last part I did the following:

  • Pick a vertex U connected to only one bridge
  • Perform a separate BFS on each neighbour of U while maintaining a shared list of visited vertices.
  • If you find another vertex V connected to a bridge, restart the current BFS from V.
  • If you’ve visited all bridge vertices when all the searches are complete, it means there is a single path that runs through all the bridges, and you can output “YES”!

AC code


#5

What testcase does my logic not saisfy?

I will count all the edges that do not create a cycle that is they simply end. To do this, I count the instances of a particular node in the input and if it is less than or equal to 1, then that particular node is an end. If we have more than two ends, answer will be “NO” else “YES”.

My code


#6

I am not getting why my code is getting run time error . What I did is count the occurrence of each edge . If there is more than 1 edge between two nodes i.e. multi-edge then I did not count it in Tarjan’s Bridge finding algorithm . For this I have maintained a map to count edges .

Then after finding all bridges I iterate over all bridges and count degree of each node that presents in bridges . Then I count the number of nodes having one degree i.e. end point of bridges . If there exist more than 2 end points of bridges i.e. more than 2 nodes having degree equals to 1 then print “NO” because we can’t cover more than two end point via single new edge .

But I am not getting why my code getting run time error ?

Wrong Solution


#7

@bajjoo, the problem can’t be solved in that way. Even I tried to solve it in that manner. But after 2 WAs, I got the wrong test case.

6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6

something like this:

1---2
 \ /
  3
  |
  4
 / \
5---6

#8

Solutions by Author and Tester are not visible. Please fix them.


#9

i have already mentioned that in the last part of the editorial.


#10

Please check, its visible


#11

“However, structures like hashmaps can do away with the extra log⁡N factor”
Edge-List != Hashmap : Hashmaps have some large constant associated with them.

Edge-list is simply storing the edge-ids in the adjacency list instead of neighbours: It can be used to handle multi-edges.


#12

(https://www.codechef.com/viewsolution/10621412)

#13

ya but its one and the same thing. I mean the concept is pretty similar.


#14

@bajjoo, the problem can’t be solved in that way. Even I tried to solve it in that manner. But after 2 WAs, I got the wrong test case.
6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6
1—2
\ /
3
|
4
/
5—6