求無向圖的割點
割點（cut vertex），或者稱作割頂更為确切。對于聯通圖，割點就是删除之後使圖不在連通的點，橋就是删除之後使圖不連通的邊。
POJ1144
裸題，解析看後面。
#include<iostream>
#include<cstdio>
#include<vector>
#include<sstream>
#include<cstring>
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
const int N = 110;
vector<int>G[N];
int pre[N];
int low[N];
bool iscut[N];
int dfs_num;
void init(){
mem(pre,0); mem(low,0);mem(iscut,0);
for(int i=0;i<N;i++) G[i].clear();
dfs_num = 0;
}
int dfs(int u,int fa){
low[u] = pre[u] = ++dfs_num;
int child = 0;
for(int i=0;i<G[u].size();i++){
int v = G[u][i];
if(!pre[v]){
child++;
dfs(v,u);
low[u] = min(low[u],low[v]);//用後代的low更新目前的
if(low[v] >= pre[u])
iscut[u] = 1;
/* if(low[v] > pre[u])
iscutbridge = 1;
*/
}
else if( v != fa)
low[u] = min(low[u],pre[v]);//利用後代v的反向邊更新low
}
if(fa< 0 && child == 1) iscut[u] = 0;//就一個後代（共兩個節點）
}
int main(){
int t;
while(scanf("%d",&t)!=EOF&&t){
init();
int n;
getchar();
string tmp;
while(getline(cin,tmp)){
int l,r;
stringstream ss(tmp);
ss>>l;
if(!l) break;
while(ss>>r){
G[l].push_back(r);
G[r].push_back(l);
}
}
for(int i=1;i<=t;i++){
if(!pre[i])
dfs(i,-1);
}
int ans = 0;
for(int i=1;i<=t;i++){
if(iscut[i])
ans++;
}
printf("%d\n",ans);
}
return 0;
}
求無向圖的橋
tarjan算法裡教我們隻要 low[v] > pre[u],即v的後代正能連回v自己，那麼（u，v）就是橋，但是這種方法并不常用，因為他隻能适用于無重邊的情況。
對于求割點，我們用兩條反向邊建立無向圖（圖1）。
圖1
圖2
因為一條邊我們會處理兩次，是以我們在dfs（int u,int fa）,這個參數中存入了fa（父節點）用來判斷是否是第二次處理了這條邊
else if( v != fa)
low[u] = min(low[u],pre[v]);//利用後代v的反向邊更新low
即這句話。也就保證了一條邊不會回頭走（回頭走但并不會更新low數組）。
但是如果出現了重邊。如圖2
按照上面的方法我們仍然不去走這些這些反向箭頭， 我們就會漏掉了重邊，求出了f 到 v1 是橋這一錯誤結果（顯然 f 到 v1因為重邊的存在并不是橋）。
因而對于求橋，我們不能再用求割點的方法dfs（int u，int fa），
我們需要走重邊，但是不要走同一條邊的反向箭頭。
解決方法：
我們對所有的邊編号，如果發現是同一條邊，我們就continue；（解決了不走同一條邊的反向箭頭）
dfs（int u，int fa），fa的位置不在儲存u節點的父親節點， 而是儲存 u 節點的父親邊。
int id = G[u][i].id;
if(id == fa) continue;
id為目前邊的編号，如果是同一條邊，則直接continue；
習題：HDU4738
#include<iostream>
#include<cstdio>
#include<vector>
#include<sstream>
#include<cstring>
#include<algorithm>
#define mem(a,x) memset(a,x,sizeof(a))
#define INF 0x3f3f3f3f
using namespace std;
const int N = 1010;
struct node{
int v,w,id;
node(int v = 0,int w = 0,int id = 0):v(v),w(w),id(id){};
};
vector<node>G[N];
int pre[N];
int low[N];
int dfs_num;int ans ;int n,m;
void init(){
mem(pre,0); mem(low,0);
for(int i=0;i<=n;i++) G[i].clear();
dfs_num = 0;ans = INF;
}
int dfs(int u,int fa){
low[u] = pre[u] = ++dfs_num;
for(int i=0;i<G[u].size();i++){
int v = G[u][i].v;
int id = G[u][i].id;
if(id == fa) continue;
if(!pre[v]){
dfs(v,id);//注意這裡 第二個參數是 id
low[u] = min(low[u],low[v]);//用後代的low更新目前的
if(low[v] > pre[u])
ans = min(ans,G[u][i].w);
}
else
low[u] = min(low[u],pre[v]);//利用後代v的反向邊更新low
}
}
int main(){
int t;
while(scanf("%d%d",&n,&m)!=EOF&& (n || m)){
int a,b,c;
init();
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
G[a].push_back(node(b,c,i));
G[b].push_back(node(a,c,i));
}
int cnt = 0;
for(int i=1;i<=n;i++){
if(!pre[i]){
cnt++;
dfs(i,0);
}
}
if(cnt > 1) //多于一個聯通分量 不用派人
ans = 0;
else if(ans == INF)
ans = -1;
else if(ans == 0) // 沒有人看守，也需要派一個人去炸橋
ans = 1;
printf("%d\n",ans);
}
return 0;
}