poj1741，poj 3177 Redundant Paths（tarjan邊雙連通）

題目鏈接：http://poj.org/problem?id=3177

題意：求最少加幾條邊使得沒對點都有至少兩條路互通。

?

poj1741？題解：邊雙連通顧名思義，可以先求一下連通塊顯然連通塊里的點都是雙連通的，然后就是各個連通塊之間的問題。

也就是說只要求一下橋，然后某個連通塊橋的個數位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;
}