PROBLEM LINK:Author: Tuan Anh Tran Dang DIFFICULTY:Hard PREREQUISITES:DFS order PROBLEM:Given an undirected simple graph with N nodes and M edges, find how many pairs of edges are fatal. A pair of edges are fatal if and only if the graph will be disconnected after we removed them. EXPLANATION:First of all, a trivial case is that, the given graph is disconnected. In such case, the answer should be M * (M  1) / 2. Therefore, we only concern the connected graph. Because of the connectivity, we can find a spanning tree first. Then, all edge can be classified into two sets: (1) TreeEdge, (2) NonTreeEdge. If we remove two NonTreeEdges, obviously, the graph will be still connected. If any TreeEdge is removed, the connectivity depends on whether there are still some NonTreeEdges connect the two parts separated by this TreeEdge in the spanning tree. Let's have a example as following (same as the sample input). Since the spanning tree can be chosen in any way, we choose the DFSTree starting from node 1 for the convenience (we will state the convenience later). In this example, we can see that there are two NonTreeEdges (labeled as 1 and 2). And then, for each TreeEdge, it is labeled by a set of NonTreeEdges which are crossing the edge. That is, if we delete that TreeEdge, the NonTreeEdges in that set will connect the two separated parts. For a given NonTreeEdge, it will take care of a path on the DFSTree. Furthermore, in the DFSTree, there are only "children > ancestor" NonTreeEdges (i.e. back edges. This provides some conveniece). Based on this label system, the forbidden pairs of edges are those edges with same label or some edge with empty set. For the first case, that is they depends on the same set of NonTreeEdges, after removing them together, the NonTreeEdges are not able to connect the three parts of tree (or the NonTreeEdge which is needed to connect the two parts are deleted). For the second case, edges with empty set as labels are all cuts, i.e. removing them will lead to disconnected state. Therefore, our task is now focused on calculating the label of each edge. For a simple hash idea and the perfect (perfect because x xor x = 0) operation XOR, we can set a random number ranging from 1..2^64  1 to each NonTreeEdges. And then, represent a set of numbers as their XOR sum. That is, if a set is {1, 3}, the label will be treated as 2 (since 1 xor 3 = 2). Two sets are identical, if and only if their labels are same (high probability correct). Finally, the only obstacle comes that how to XOR a number x to the edges between node u and v for all NonTreeEdges. And we need to query the XOR sum after all operations for all TreeEdges. Thanks to the DFSTree we selected, without loss of generality, we suppose u is an ancestry of v. Denote prefix[u] as the XOR sum added to the path from root 1 to node u. Adding x to the path between u and v is equivalent to
And after all NonTreeEdges are added to their corresponding paths on the DfSTree, we traverse the DFSTree again and can get the label on all TreeEdges (it depends on the XOR sum of prefix[] in its subtree). In the end, what we need is to count the number of pairs of labels, which are same or at least one zero. This could be done by hash too. In summary, we have a O(N + M) algorithm to solve this problem with a high probability (due to the randomness to choose the NonTreeEdges' labels). Because 2^64 is large enough comparing to the range of N and M, don't worry about the probability. :) You will get AC if you implemented correctly. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 13 Jan '14, 15:13

Our graph is connected. So first statement is unnecessary. answered 13 Jan '14, 16:48

Here is once more nice test which fails at least one of accepted top solutions:
answered 13 Jan '14, 18:06

UPD. THE SOLUTION BELOW IS WRONG!!!I have completely different solution with complexity O(M * log M).
You can find implementation details in my solution. answered 14 Jan '14, 13:48
3
What if you don't have vertices of degree 2? The answer still can be nonzero (see the test case below by lgsmitty).
(14 Jan '14, 23:37)

Finally, the only obstacle comes that how to XOR a number x to the edges between node u and v for all NonTreeEdges. And we need to query the XOR sum after all operations for all TreeEdges. Thanks to the DFSTree we selected, without loss of generality, we suppose u is an ancestry of v. Denote prefix[u] as the XOR sum added to the path from root 1 to node u. Adding x to the path between u and v is equivalent to I have two doubts in the solution provided. First : Can anyone please explain why there is a need to have prefix[u]. All I have understood is that all the back edges get random number between 0 and 2^64  1 and all the dfstree edges gets a label from whatever backedges is crossing. Now the fatal edges are those having same labels. Second : How removing of dfstree edges makes the graph unconnected ? answered 12 Feb '14, 23:50

I worked with the problem setter during the preparation of the contest and we also have fully deterministic solutions with O((N+M) * sqrt(N)) and O(N+M) * log(N)) time complexities (the time limit was set in order to allow both such types of solutions to pass). The solution described in the editorial is, however, the simplest in terms of implementation. I only wrote this comment in order to let you know that this is not the only known solution.
Sure, sure. I think we can start from this method to find a fully deterministic solution with linear time.