Problem G

Doves and Bombs

Input: Standard Input

Output: Standard Output

Time Limit: 2 Seconds

It is the year 95 ACM (After the Crash of Microsoft). Aftermany years of peace, a war has broken out. Your nation, the islandof Evergreen Macros And Confusing Shortcuts(EMACS), is defending itself against the railway empire ruled by VisuallyImpaired Machinists (VIM).

In the days leading up to the outbreak ofwar, your government devoted a great deal of resources toward gatheringintelligence on VIM. It discovered the following:

• The empire has a large network of railway stations connected by bidirectional tracks.
• Before the outbreak of the war, each railway station was directly connected to at most 10 other stations.
• Information is constantly being exchanged in VIM, but, due to a design flaw, the only way it can be exchanged is to send the messages by train. Before the outbreak of the war, it was possible to send a message by train from any station to any other station.
• As a last resort, the empire's central command can send messages by carrier pigeon, but it tries to avoid this at all costs, as the only pigeons suitable for the job must be imported, at great expense, from the far-away land of Pigeons In Courier Outfits (PICO).
• Once a pigeon has delivered a message to a railway station, it must rest, and thus cannot be used again. If a pigeon has delivered a broadcast message to a particular station, the message is passed on, if possible, by train.

Based on this information, the governmentof EMACS has come up with a plan to disrupt the activities of the evil empire.They will send bomber planes to bomb the railway stations, thus hamperingcommunications in the empire. This will necessitate to acquire many carrierpigeons by the empire, distracting it from its deadly wartime activities.

Unfortunately, your government spent somuch money on gathering intelligence that it has a very limited amount left tobuild bombs. As a result, it can bomb only one target. You have been chargedwith the task of determining the best candidate railway stations in the empireto bomb, based on their "pigeon value". The "pigeon value"of a station is the minimum number of pigeons that after bombing this station,will be required to broadcast a message from the empire central command to allnon-bombed stations. The location of the empire central command is unknown butwe know that it is not located at a railway station. This implies, that whenthe central command needs to send a message to some non-bombed station they haveto use at least one pigeon and then the message can be further transmitted bythe railway.

Input

The input file contains several test cases. Thedata for each case begins with a line containing the following two integers:

• n the number of railway stations in the empire (3 ≤ n ≤ 10000). The stations will be numbered starting from 0, up to n-1 .
• m the number of stations to be identified as candidate bombing targets (1 ≤ m ≤ n).

Next few lines consists of pairs of integers.Each pair (x,y) indicates the presence of a bidirectionalrailway line connecting railway stations x and y.  This sequence is terminated by a linecontaining two minus 1 as shown in the sample input.

Input is terminated by a case where the value ofn=m=0. This case should not be processed.

Output

Sample Input                             Output for Sample Input

Problemsetter:Paul Shelly

題目描述；

當沒有鐵路進行溝通時，訊息將由鴿子來傳輸，訊息盡可能藉由鐵路來傳輸。

因此當一個火車站被摧毀時，會將連通圖破壞成數個連通圖，而這幾個連通圖將會用鴿子互相傳輸資料。

但只能摧毀一個火車站的情況下，需要評估其價值，因此定義鴿子點為會破換成幾個連通圖。

輸出前 K 大的鴿子點。

題目解法：

利用 dfs 生成樹形，然後檢查 back edge 藉此得到關節點，同時也會找到"橋"，

每發現一個橋，則對於兩端的鴿子點都會+1，其中一點破壞時，都會多造成一個連通圖。

特別要考慮一個情況，剩餘非橋的部分是否存在，如果存在則額外加一。

最後排序輸出前 m 個。

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[10005];
int vfind[10005], visited[10005], findIdx;
struct E {
    int x, value;
    bool operator<(const E &a) const {
        if(value != a.value)
            return value > a.value;
        return x < a.x;
    }
};
E D[10005];
int dfs(int nd, int p) {
    visited[nd] = 1;
    vfind[nd] = ++findIdx;
    int mn = vfind[nd];
    int i;
    for(i = 0; i < g[nd].size(); i++) {
        if(!visited[g[nd][i]]) {
            int b = dfs(g[nd][i], nd);
            if(b > vfind[nd]) {//bridge
                D[nd].value++;
                D[g[nd][i]].value++;
            }
            mn = min(mn, b);
        } else {
            if(g[nd][i] != p) {
                mn = min(mn, vfind[g[nd][i]]);
            }
        }
    }
    return mn;
}
int main() {
    int n, m;
    int i, j, k, x, y;
    while(scanf("%d %d", &n, &m) == 2 && n) {
        for(i = 0; i < n; i++) {
            g[i].clear(), visited[i] = 0;
            D[i].x = i, D[i].value = 0;
        }
        while(scanf("%d %d", &x, &y) == 2 && x >= 0) {
            g[x].push_back(y);
            g[y].push_back(x);
        }
        findIdx = 0;
        for(i = 0; i < n; i++)
            if(visited[i] == 0)
                dfs(i, -1);
        for(i = 0; i < n; i++) {
            if(D[i].value != g[i].size())
                D[i].value++;
        }
        sort(D, D+n);
        for(i = 0; i < m; i++)
            printf("%d %d\n", D[i].x, D[i].value);
        puts("");
    }
    return 0;
}