题目链接：http://poj.org/problem?id=3177

题意：求最少加几条边使得没对点都有至少两条路互通。

题解：边双连通顾名思义，可以先求一下连通块显然连通块里的点都是双连通的，然后就是各个连通块之间的问题。

也就是说只要求一下桥，然后某个连通块桥的个数位1的总数，结果就是（ans+1）/2。为什么是这个结果自行画图

理解一下，挺好理解的。

#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int N = 1e5 + 10;const int M = 2e5 + 10;struct TnT {    int v , next;    bool cut;}edge[M];int head[N] , e;int Low[N] , DFN[N] , Stack[N] , Belong[N];bool Instack[N];int Index , top , bridge , block;void init() {    memset(head , -1 , sizeof(head));    e = 0;}void add(int u , int v) {    edge[e].v = v , edge[e].next = head[u] , edge[e].cut = false , head[u] = e++;}void Tarjan(int u , int pre) {    int v;    Low[u] = DFN[u] = ++Index;    Stack[top++] = u;    Instack[u] = true;    for(int i = head[u] ; i != -1 ; i = edge[i].next) {        v = edge[i].v;        if(v == pre) continue;        if(!DFN[v]) {            Tarjan(v , u);            Low[u] = min(Low[u] , Low[v]);            if(Low[v] > DFN[u]) {                bridge++;                edge[i].cut = true;                edge[i^1].cut = true;            }        }        else if(Instack[v]) Low[u] = min(Low[u] , DFN[v]);    }    if(Low[u] == DFN[u]) {        block++;        do {            v = Stack[--top];            Instack[v] = false;            Belong[v] =  block;        } while(v != u);    }}int du[N];int main() {    int f , r;    while(~scanf("%d%d" , &f , &r)) {        init();        for(int i = 0 ; i < r ; i++) {            int u , v;            scanf("%d%d" , &u , &v);            add(u , v);            add(v , u);        }        memset(DFN , 0 , sizeof(DFN));        memset(Instack , false , sizeof(Instack));        memset(du , 0 , sizeof(du));        Index = 0 , block = 0 , top = 0;        for(int i = 1 ; i <= f ; i++)            if(!DFN[i]) Tarjan(i , i);        for(int i = 1 ; i <= f ; i++) {            for(int j = head[i] ; j != -1 ; j = edge[j].next) {                if(edge[j].cut) {                    du[Belong[i]]++;                }            }        }        int ans = 0;        for(int i = 1 ; i <= block ; i++) {            if(du[i] == 1) {                ans++;            }        }        printf("%d\n" , (ans + 1) / 2);    }    return 0;}

poj 3177 Redundant Paths（tarjan边双连通）