×

# TAPAIR - Editorial

Author: Tuan Anh Tran Dang
Tester: Gerald Agapov
Editorialist: Jingbo Shang

Hard

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) Tree-Edge, (2) Non-Tree-Edge.

If we remove two Non-Tree-Edges, obviously, the graph will be still connected. If any Tree-Edge is removed, the connectivity depends on whether there are still some Non-Tree-Edges connect the two parts separated by this Tree-Edge 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 DFS-Tree starting from node 1 for the convenience (we will state the convenience later).

In this example, we can see that there are two Non-Tree-Edges (labeled as 1 and 2). And then, for each Tree-Edge, it is labeled by a set of Non-Tree-Edges which are crossing the edge. That is, if we delete that Tree-Edge, the Non-Tree-Edges in that set will connect the two separated parts. For a given Non-Tree-Edge, it will take care of a path on the DFS-Tree. Furthermore, in the DFS-Tree, there are only "children --> ancestor" Non-Tree-Edges (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 Non-Tree-Edges, after removing them together, the Non-Tree-Edges are not able to connect the three parts of tree (or the Non-Tree-Edge 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 Non-Tree-Edges. 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 Non-Tree-Edges. And we need to query the XOR sum after all operations for all Tree-Edges. Thanks to the DFS-Tree 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

prefix[u] = prefix[u] xor x;
prefix[v] = prefix[v] xor x


And after all Non-Tree-Edges are added to their corresponding paths on the DfS-Tree, we traverse the DFS-Tree again and can get the label on all Tree-Edges (it depends on the XOR sum of prefix[] in its sub-tree).

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 Non-Tree-Edges' 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.
Tester's solution can be found here.

This question is marked "community wiki".

161446376
accept rate: 0%

19.8k350498541

1

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.

(13 Jan '14, 17:11)
1

Sure, sure. I think we can start from this method to find a fully deterministic solution with linear time.

(14 Jan '14, 11:41)

 8 This was a very nice problem, but the test cases for it are ridiculously bad. After seeing a clearly wrong solution among the accepted ones I tested top solutions with what in my mind is a simplest non-trivial case, which is a graph like this: *--*--*--* | | | | *--*--*--*  Here, the answer should be 7. However, half of the top 12 solutions fail on this case alone. answered 13 Jan '14, 17:28 6★vytenis 121●1●1●2 accept rate: 0% ... guilty (14 Jan '14, 06:31) samjay5★ 2 Not guilty :P (14 Jan '14, 13:02) Actually, this test was the basic test in mind for designing my solution posted below. (14 Jan '14, 13:53) Not guilty either :D Beside the sample, I only tested on trees and cliques... (14 Jan '14, 15:40) xellos07★
 2 Our graph is connected. So first statement is unnecessary. answered 13 Jan '14, 16:48 161●1●4 accept rate: 20%
 2 Here is once more nice test which fails at least one of accepted top solutions: *-*-*-* |x| |x| *-*-*-*  answered 13 Jan '14, 18:06 5★lgsmitty 31●2 accept rate: 0%

## UPD. THE SOLUTION BELOW IS WRONG!!!

I have completely different solution with complexity O(M * log M).
Note that the graph is connected, so N <= M+1 and we could not include it into complexity.

• At first I divide the graph into biconnected components and count number of bridges, say B.
• Just to clarify, biconnected component does not have articulation points.
• Then due to obvious reasons the answer is
C2(M) - C2(M-B) + Sum[CNT(cmp) : cmp is biconnected component]
where CNT(cmp) is the number of bad pairs for the biconnected component cmp.
• Now the challenge is to handle biconnected graph.
Note that if we have subpath where each vertex has degree two,
then every two edges in this path forms a bad pair.
• Let's convert this observation to working solution.
At first assign to each edge a weight, which is initially 1.
• In short, we will delete vertexes of degree 2 by replacing two edges V1 -- V -- V2 by one V1 -- V2, update the answer and the weight W(U, V) of edge U -- V will correspond to the number of accumulated edges from the initial graph.
• In detail, when we have vertex V of degree two with neighbors V1 and V2, we add to the answer W(V, V1) * W(V, V2), since every pair of original edges (E1, E2) where E1 is "from" V1 -- V and E2 is "from" V -- V2 is bad (it separates V from remaining graph).
• If V1 and V2 are the only remaining vertexes then, we add (W(V, V1) + W(V, V2)) * W(V1, V2) to the answer according to the observation above and return the answer.
• Otherwise we delete edges V1 -- V, V -- V2 and add new edge V1 -- V2 with weight equals to sum W(V, V1) + W(V, V2). But, if edge V1 -- V2 was before we set this weight to zero. Indeed, if biconnected graph has two edges (U, V) and it has at least three vertexes then deleting one edge (U, V) will left graph biconnected, so it can't be in any bad pair. Thus, setting it's weight to zero is the right thing to do to not accumulate initial edges in this accumulated edge in further considerations.
• If we end up with no vertexes of degree 2 (and thus all degrees are at least 3) the answer is zero [THIS IS WRONG for this test]
• All this can be implemented very simple using associative array from edges to weights (e.g., stl map in C++)
• Most probably we can get pure O(M) solution using linked lists in a smart way, but I don't think much in this direction.

You can find implementation details in my solution.

6.7k62119138
accept rate: 12%

3

What if you don't have vertices of degree 2? The answer still can be non-zero (see the test case below by lgsmitty).

(14 Jan '14, 23:37) 6★
 0 Finally, the only obstacle comes that how to XOR a number x to the edges between node u and v for all Non-Tree-Edges. And we need to query the XOR sum after all operations for all Tree-Edges. Thanks to the DFS-Tree 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 dfs-tree edges gets a label from whatever backedges is crossing. Now the fatal edges are those having same labels. Second : How removing of dfs-tree edges makes the graph unconnected ? answered 12 Feb '14, 23:50 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,359
×304
×54
×51

question asked: 13 Jan '14, 15:13

question was seen: 6,578 times

last updated: 22 Apr '15, 17:27