Street Directions
题意：给一个无重边的无向图，把边变成有向的，有的边可能需要变成两条有向边，使得从任何一点出发都可以到达其他所有点。
只有桥需要变成两条边，其它边dfs输出即可。
1 /************************************************************************* 2 > File Name: bb.cpp 3 > Author: yijiull 4 > Mail: 1147161372@qq.com 5 > Created Time: 2017年11月19日 星期三 19时10分33秒 6 ************************************************************************/ 7 #include <bits/stdc++.h> 8 using namespace std; 9 const int maxv = 1010; 10 const int maxe = 8010; 11 12 struct Edge{ 13 int u, v, nxt; 14 int iscut; 15 Edge(int u = 0, int v = 0, int nxt = 0, int iscut = 0) : u(u), v(v), nxt(nxt), iscut(iscut) {} 16 }e[maxe]; 17 int cnt; 18 int head[maxv]; 19 20 void init(){ 21 cnt = 0; 22 memset(head, -1, sizeof(head)); 23 } 24 void add(int u, int v){ 25 e[cnt] = Edge(u, v, head[u]); 26 head[u] = cnt++; 27 e[cnt] = Edge(v, u, head[v]); 28 head[v] = cnt++; 29 } 30 int pre[maxv], low[maxv]; 31 int dfsk; 32 void dfs(int u, int id){ 33 low[u] = pre[u] = ++dfsk; 34 for(int i = head[u]; ~i; i = e[i].nxt){ 35 int v = e[i].v; 36 if(i == (id ^ 1)) continue; 37 if(!pre[v]){ 38 dfs(v, i); 39 low[u] = min(low[u], low[v]); 40 if(low[v] > pre[u]) e[i].iscut = e[i ^ 1].iscut = 1; 41 }else{ 42 low[u] = min(low[u], pre[v]); 43 } 44 } 45 } 46 void solve(int n){ 47 memset(pre, 0, sizeof(pre)); 48 dfsk = 0; 49 for(int i = 0; i < n; i++) if(!pre[i]) dfs(i, -1); 50 } 51 int vis[maxv]; 52 void print(int u){ 53 vis[u] = 1; 54 for(int i = head[u]; ~i; i = e[i].nxt){ 55 if(e[i].iscut) continue; 56 int v = e[i].v; 57 printf("%d %d ", u + 1, v + 1); 58 e[i].iscut = e[i ^ 1].iscut = 2; 59 if(!vis[v]) print(v); 60 } 61 } 62 int main(){ 63 //freopen("in.txt", "r", stdin); 64 int n, m; 65 int kase = 0; 66 while(scanf("%d %d", &n, &m) && (n + m)){ 67 init(); 68 int u, v; 69 for(int i = 0; i < m; i++){ 70 scanf("%d %d", &u, &v); 71 u--; v--; 72 add(u, v); 73 } 74 printf("%d ", ++kase); 75 solve(n); 76 memset(vis, 0, sizeof(vis)); 77 for(int i = 0; i < n; i++) if(!vis[i]) print(i); 78 for(int i = 0; i < cnt; i++){ 79 if(e[i].iscut == 1) { 80 printf("%d %d ", e[i].u + 1, e[i].v + 1); 81 } 82 } 83 puts("#"); 84 } 85 }