Single Point of Failure

Interview

Time limit1sMemory limit128 MB

Summary
For each undirected connected graph, list every articulation point and the number of connected components its removal creates.
Level

Medium7 of 10

Topics
Graph, DFS, Implementation, Brute force
Solved
No attempts yet

Problem

In a peer-to-peer network, data can only move directly between nodes that are physically connected. If the failure of a single node would leave at least one pair of the remaining nodes unable to communicate, that node is called a Single Point of Failure (SPF).

Formally, on a network that was previously fully connected (every node could reach every other node), a node is an SPF if removing it splits the remaining nodes into two or more groups that can no longer all reach one another.

Some networks have no SPF at all: at least two nodes would have to fail before any pair of the surviving nodes becomes unreachable. For each given network, find every SPF node.

Input

The input describes several networks. Each network is a list of edges, one edge per line, where an edge is a pair of integers naming two directly connected nodes. The order within a pair is irrelevant: 1 2 and 2 1 describe the same connection. Every node number is between 11 and 10001000.

A line containing a single 0 ends the current network's edge list. An empty network description (a 0 with no preceding edges) marks the end of the input. Blank lines may appear anywhere and must be ignored.

Every network in the input is fully connected before any node fails.

Output

For each network, first print a header line Network #k, where k is the network's position in the input (the first network is Network #1, the second Network #2, and so on).

Then, for every SPF node, print one line in the form

  SPF node <node> leaves <count> subnets

(with two leading spaces), where <node> is the failing node and <count> is the number of separate fully connected subnets that remain after that node fails. List the SPF nodes in increasing order of node number.

If a network has no SPF node, print the single line No SPF nodes (two leading spaces) instead.

Print one blank line between the reports of consecutive networks.

Examples4

  1. Example 1

    Input
    1 2
5 4
3 1
3 2
3 4
3 5
0

1 2
2 3
3 4
4 5
5 1
0

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

0
    Expected output
    Network #1
  SPF node 3 leaves 2 subnets

Network #2
  No SPF nodes

Network #3
  SPF node 2 leaves 2 subnets
  SPF node 3 leaves 2 subnets

  2. Example 2

    Input
    1 2
2 3
3 4
4 5
0

0
    Expected output
    Network #1
  SPF node 2 leaves 2 subnets
  SPF node 3 leaves 2 subnets
  SPF node 4 leaves 2 subnets

  3. Example 3

    Input
    1 2
1 3
1 4
1 5
0

0
    Expected output
    Network #1
  SPF node 1 leaves 4 subnets

  4. Example 4

    Input
    1 2
2 3
3 1
0

0
    Expected output
    Network #1
  No SPF nodes