DMOPC '15 Contest 5 P6 - Event Horizon

View as PDF
Submit solution
Points: 25 (partial)
Time limit: 1.0s
Memory limit: 128M
Author:
k_53P
Problem types

Using his experiences with time travel, as well as some knowledge of general relativity and black holes, the mad scientist Kyouma has created a doomsday device. He plans to cause a localized event horizon: given a series of events and connections, sever the events so that no event can be affected by another.

Kyouma has spotted a network of events which he will use his device on. This network can be treated as an undirected graph with N vertices (numbered from 1 to N) and M edges, with each vertex representing an event to disconnect and each edge representing a connection between two events. When Kyouma triggers his device, a large distortion in spacetime is created, allowing him to remove any group of edges from the graph which forms a pseudoforest. He considers the network destroyed and his task complete once he has removed all edges through uses of his doomsday device.

However, some of the connections between events are abnormally strong: that is, it is possible for multiple edges to exist between the same pair of vertices, all of which must be removed. It is guaranteed that each edge connects two distinct vertices.

Kyouma, while an evil genius, is neither very rich nor very patient. Therefore, he would like to know the fewest number of times he must activate his device to destroy the network.

Note

A pseudoforest is a series of edges where, for each connected component, there is at most one simple cycle. Since there may be repeated edges in this graph, a simple cycle contained in a valid pseudoforest may consist of two vertices connected by two edges.

Constraints

For all subtasks:

1 \le a,b \le N

a \ne b

Subtask 1 [10%]

1 \le M \le 9

2 \le N \le 9

Subtask 2 [90%]

1 \le M \le 2000

2 \le N \le 2000

Input Specification

On the first line will be two space separated integers: N, the number of vertices, and M, the number of edges.

On each of the next M lines, there will be two integers a and b, indicating a two-way connection between a and b.

Output Specification

Print a single integer, the fewest number of pseudoforests that must be removed in order to disconnect all vertices.

Sample Input 1

3 2
1 2
3 2

Sample Output 1

1

Sample Input 2

4 5
1 2
2 3
3 4
4 1
1 3

Sample Output 2

2

Explanation for Sample 2

There is no way to remove all the edges with one pseudoforest. To remove it with two, Kyouma could for example remove the edges (1,2) and (2,3) at first, and then remove the remaining edges afterwards.

Sample Input 3

2 2
1 2
1 2

Sample Output 3

1

Explanation for Sample 3

As can be seen, a cycle between two nodes (1 and 2 in this case) is considered a valid cycle, and can therefore be removed in one activation.

Sample Input 4

3 4
1 2
2 1
2 3
3 2

Sample Output 4

2

Comments


  • 0
    kobortor  commented on Feb. 10, 2016, 12:05 a.m. ← edit 5 
    6 9
1 2
1 3
2 3
2 4
3 4
3 5
4 5
4 6
5 6

    • 1
      k_53P  commented on Feb. 10, 2016, 12:38 a.m.

      I can only say that the answer to that case (assuming that line breaks are inserted and spaces deleted where necessary) exists and is unambiguous. Is there any particular clarification that would be answered by that case?


      • 0
        kobortor  commented on Feb. 10, 2016, 12:45 a.m.

        Yeah I'm not exactly understanding how Kyouma "removes" pseudoforests. Can you explain how he would do it here for the best result?


        • 0
          k_53P  commented on Feb. 10, 2016, 12:56 a.m. ← edited

          He removes a subset of edges from the graph. From your example, he could remove the edges (1,2), (2,3) and (1,3) at once with one use of the machine, because those edges form a valid pseudoforest. Each edge must be removed at some point in time. (This does not necessarily lead to a correct answer, it is just an example.)