Tarjan算法寻找无向图中的桥（割边）

桥的定义：
对于一个无向图，如果移除某一条边后，它的联通块的数量增加了，那么这条边就叫做桥，或者叫割边。也可以这么说，在无向图中，如果移除一条边之后，原来可以互达的两个点不再可达了，那么这个边就叫做桥。

根据定义，在联通的无向图中，要判断一条边是否是桥，只需要把这条边移除，然后从某个点遍历全图，如果遍历后还有点没有访问，那么这条边就是桥。这个算法的复杂度取决于遍历的复杂度，如果使用邻接表+BFS，则复杂度为O(|V| + |E|) .

同样的，要找出一张联通无向图的所有桥，可以用以上方法依次测试每条边。不过，复杂度就提升到O(|E|^2 + |V||E|)了，对于边数超过10000的图就不再适用了。

Tarjan算法可以在O(|E| + |V|) 的时间内求出无向图中所有的桥。基本框架如下：

ord表示一条边的标号，一条无向边拆成的两条有向边的ord相同。

C语言: 高亮代码由发芽网提供

void tarjan(long x,long f)
{
   node *p;
   T ++;
   dfsn[x] = low[x] = T;
   for(p = first[x];p != NULL;p = p->next)
       if(p->ord != f)
       {
           if(dfsn[p->v] == 0)   //还未访问
           {
               tarjan(p->v,p->ord);
               low[x] = getmin(low[x],low[p->v]);
               if(dfsn[x] < low[p->v])
                   cut[p->ord] = 1;
           }
           else
               low[x] = getmin(low[x],dfsn[p->v]);
       }
}

需要注意的是，上面函数的第二个参数f记录的是到达x点的边的标号，这样，即使存在重边，Tarjan也可以正常工作。如果f表示的是走到x的前一个点，那么重边会被误判为桥。

对于Tarjan算法是如何找出桥的，读者可以自己模拟。

下面是本人的思路：
由于使用DFS，因此遍历过的一定是一棵树。如果两个联通块之间只有一条路径（桥），那么DFS走过去之后就一定不会再走回来（除非退回来），并且由于Tarjan不允许直接从父亲更新（p->ord != f）。故桥两端的点i，j就会出现dfsn[i] < low[j]的情况。