VM7WC '16 #6 Gold - Cold War Telecom

View as PDF
Submit solution
Points: 10
Time limit: 1.0s
Memory limit: 64M
Author:
JeffreyZ
Problem type

In the 1960s, long distance telecommunications in North America was handled by a single company: AT&T. No other company had established the network to do so, and with good reason: the AT&T network was enormous and extensive. Here is a map of the AT&T microwave radio network that spanned across both the United States and Canada, transcribed on March 15th, 1960 (open the full size image):

This was known as the AT&T long lines network. You will be given a graph that will represent this network, with N nodes and M edges. Though AT&T only had around a thousand nodes, in our graph 1 \le N \le 10^5 and 1 \le M \le 10^6. No node will connect to itself. Initially, there is a path between every pair of nodes, which means that every node can communicate with every other node. Each edge will be bidirectional.

If you were using a phone or television during anytime during the sixties, the underlying telecom was most likely handled by AT&T. The sixties was also the time of the Cold War, and was marked by a fear of nuclear war with the Soviet Union. In an event of a nuclear attack, communication across the country would be crucial for things such as the Ballistic Missile Early Warning System (BMEWS) and the Emergency Broadcast System (EBS). Due to AT&T's monopoly over telecom, the US government relied on its network to ensure that these systems would stay in communication.

To prepare for nuclear war, all AT&T network towers were reinforced to withstand a nuclear blast from a radius of five miles. Some nodes were deemed as crucial to the AT&T network, such that, if a crucial network was to be deliberately targeted by the Soviet Union and destroyed during the attack, two other nodes will no longer be able to communicate with each other. If a network tower belonged to a crucial node, the dependent buildings and machinery were moved underground and made even more resistant to a nuclear explosion.

A quick glance at the map reveals that there are many such crucial nodes, but the US government ignored those that broke the connection between less important places. For the sake of this problem, all nodes that, if destroyed, break the connection between two other nodes are deemed crucial. Given a graph, find all crucial nodes so that the US government knows which sites to reinforce.

Input Specification

On the first line will be two positive integers N and M, the number of nodes and the number of edges within the AT&T network. The next M lines will each contain two positive integers x and y (1 \le x, y \le N), denoting the numbers of nodes that are connected.

Output Specification

On the first line, print the number of crucial nodes in the network. The following lines should contain the numbers of the crucial nodes, one per line and in increasing order.

Sample Input

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

Sample Output

2
1
4

Comments


  • 0
    jlsajfj  commented on Feb. 13, 2016, 2:06 a.m.

    Can there be repeats of a connection? ie. Input: 2 4 1 2 2 1 1 2 2 1


    • -1
      jeffreyxiao  commented on Feb. 13, 2016, 2:25 a.m.

      I don't think it matters


  • 11
    fsdom  commented on Feb. 12, 2016, 6:49 p.m.

    Can someone help me to understand the problem in easy English and short description?


    • 28
      jeffreyxiao  commented on Feb. 12, 2016, 7:32 p.m.

      Find the number of articulation points in a graph.