CF 118E

首先这个题目需要去判断原图是否是一个双连通分量，因为如果不是双连通分量的话，那么最后在桥的位置就是单向的，只能由一块走到另一块，而不能由另一块走回来。同时，如果原图是双连通分量，那么就一定有解，因为至少存在一个欧拉回路，而其他路的方向就无所谓了，因此在输出的时候只要用dfs顺序将每个边输出一次即可。

但问题在于如果分两块去做——先用tarjan判双连通、然后dfs打印路径，这样会超时，我们反思一下判双连通时tarjan算法的本质就是一个dfs，因此我们在判双连通的时候不妨先把各个需要打印的边存下来，如果最后有解就顺序输出即可，这样就节省了不少的时间。

#include
     
       #include
      
        #define MAXD 100010 #define MAXM 600010 int N, M; int first[MAXD], op[MAXM], next[MAXM]; int v[MAXM] ,ansx[MAXM], ansy[MAXM], vis[MAXM]; int dfn[MAXD], low[MAXD], cnt, col, res; void init() {
   int i, e, tx, ty, x, y; for(i = 1; i <= N; i ++)         first[i] = -1;     e = 0; for(i = 0; i < M; i ++)     {
           scanf("%d%d", &x, &y);         v[e] = y;         next[e] = first[x];         first[x] = e;         op[e] = e + 1;         e ++;         v[e] = x;         next[e] = first[y];         first[y] = e;         op[e] = e - 1;         e ++;     } } int tarjan(int u, int fa) {
   int e;     dfn[u] = low[u] = ++ cnt; for(e = first[u]; e != -1; e = next[e]) if(v[e] != fa)         {
   if(!dfn[v[e]])             {
   if(!tarjan(v[e], u)) return 0; if(low[v[e]] < low[u])                     low[u] = low[v[e]]; else if(low[v[e]] > dfn[u])                 {
                       col ++; return 0;                 }             } else if(dfn[v[e]] < low[u])                 low[u] = dfn[v[e]]; if(!vis[e])             {
                   vis[e] = vis[op[e]] = 1;                 ansx[res] = v[e];                 ansy[res] = u;                 res ++;             }         } return 1; } int judge() {
   int u; for(u = 1; u <= N; u ++)         dfn[u] = 0;     cnt = col = 0;     res = 0; for(u = 1; u <= N; u ++) if(!dfn[u]) if(col || !tarjan(u, -1)) return 0; return 1; } int main() {
   int i, tot; while(scanf("%d%d", &N, &M) == 2)     {
           init();         tot = 2 * M; for(i = 0; i < tot; i ++)             vis[i] = 0; if(!judge())             printf("0\n"); else         {
   for(i = 0; i < M; i ++)                 printf("%d %d\n", ansx[i], ansy[i]);         }     } return 0; }