Street Directions

According to the Automobile Collision Monitor (ACM), most fatal traffic accidents occur on two-way streets. In order to reduce the number of fatalities caused by traffic accidents, the mayor wants to convert as many streets as possible into one-way streets. You have been hired to perform this conversion, so that from each intersection, it is possible for a motorist to drive to all the other intersections following some route.

You will be given a list of streets (all two-way) of the city. Each street connects two intersections, and does not go through an intersection. At most four streets meet at each intersection, and there is at most one street connecting any pair of intersections. It is possible for an intersection to be the end point of only one street. You may assume that it is possible for a motorist to drive from each destination to any other destination when every street is a two-way street.

Input 

The input consists of a number of cases. The first line of each case contains two integers n and m. The number of intersections is n ( ), and the number of streets is m. The next m lines contain the intersections incident to each of the m streets. The intersections are numbered from 1 to n, and each street is listed once. If the pair is present, will not be present. End of input is indicated by n = m = 0.

Output 

For each case, print the case number (starting from 1) followed by a blank line. Next, print on separate lines each street as the pair to indicate that the street has been assigned the direction going from intersection i to intersection j. For a street that cannot be converted into a one-way street, print both and on two different lines. The list of streets can be printed in any order. Terminate each case with a line containing a single `#' character.

Note: There may be many possible direction assignments satisfying the requirements. Any such assignment is acceptable.

Sample Input 

7 10
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
2 5
3 6
7 9
1 2
1 3
1 4
2 4
3 4
4 5
5 6
5 7
7 6
0 0

Sample Output 

1

1 2
2 4
3 1
3 6
4 3
5 2
5 4
6 4
6 7
7 5
#
2

1 2
2 4
3 1
4 1
4 3
4 5
5 4
5 6
6 7
7 5
#

---

Miguel A. Revilla
1999-03-24

題目描述：
給定一些道路，一開始全部是雙向連通，由於交通混亂，盡可能將道路改成單向。
在不改變連通性的情況下，而且原本的道路都要保留，最後最少(以單向表示)的道路為何？

題目解法：
考慮連通性的情況下，找橋也將當重要，補充說明：關節點跟橋有關係。

由於橋是溝通兩個元件的唯一橋梁，因此橋一定是雙向的。

而其它路徑則根據 dfs 搜索出來的樹形建立一個單向道路。

back edge 是由下往上，而其他道路則是由上往下的單向。

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[1005];
int vfind[1005], visited[1005], findIdx;
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
                printf("%d %d\n", nd, g[nd][i]);
                printf("%d %d\n", g[nd][i], nd);
            } else {
                printf("%d %d\n", nd, g[nd][i]);
            }
            mn = min(mn, b);
        } else {
            if(g[nd][i] != p) {
                if(vfind[nd] >= vfind[g[nd][i]])
                    printf("%d %d\n", nd, g[nd][i]);
                mn = min(mn, vfind[g[nd][i]]);
            }
        }
    }
    return mn;
}
int main() {
    int n, m, cases = 0, i, x, y;
    while(scanf("%d %d", &n, &m) == 2 && n) {
        for(i = 1; i <= n; i++)
            g[i].clear(), visited[i] = 0;
        while(m--) {
            scanf("%d %d", &x, &y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        printf("%d\n\n", ++cases);
        for(i = 1; i <= n; i++) {
            if(visited[i] == 0) {
                findIdx = 0;
                dfs(i, -1);
            }
        }
        puts("#");
    }
    return 0;
}