简单的理解：
割点：在一个连通图中，去掉一点能使图变成多个连通块的点叫割点；
桥就是去掉一边能使图变成多个联通块的边
求法：
割点：
（1）u为树根时，且u有多于一个子树。
（2）u不为树根，且满足存在 low[v]>=dfn[u]。 则u是割点。
桥：当low[v]>dfn[u]时，边（u，v）、（v，u）就是桥
理解：dfn[u] 为时间戳，就是第几个搜索到点u, low[u]是u或u的子树中通过非父子边（返祖边）追溯到最早的节点。
当low[v] >=dfn[u] 时，说明v及v的子树是不能通过返祖边找到比 u更早的边，即点u将 v和v的子树 与 u之前的边隔开。所以u是割点
low[v]>dfn[u]也是如此。但是 当low[v]==dfn[u]时，v和v的子树时达到u,说明他们是同一个连通分量，所以没有桥。
代码模板：
/* 1.可以求出图的割点和桥 2.可以求删除每个点后增加的连通块 */ #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<queue> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=10010; const int maxm=200100; struct node{ int u,v,nxt; bool cut;//记录是否是桥 }e[maxm]; int h[maxn],cnt; int low[maxn],dfn[maxn],st[maxn],tot,top; bool instack[maxn]; bool cut[maxn];//记录是否是割点 int add_block[maxn];//删除一个点后增加的连通块 int bridge;//记录桥的条数 void add(int u,int v) { e[cnt].u=u;e[cnt].v=v;e[cnt].cut=0; e[cnt].nxt=h[u];h[u]=cnt++; } void tarjan(int u,int pre) { low[u]=dfn[u]=++tot; st[top++]=u; instack[u]=1; int son=0; int pre_cnt=0;//处理重边 for(int i=h[u];i!=-1;i=e[i].nxt) { int v=e[i].v; if(v==pre&&pre_cnt==0) { pre_cnt++; continue; } if(!dfn[v]) { son++; tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>dfn[u])//桥 { bridge++; e[i].cut=1; e[i^1].cut=1; } if(u!=pre&&low[v]>=dfn[u])//非树根，割点 { cut[u]=1; add_block[u]++; } } else low[u]=min(low[u],dfn[v]); } if(u==pre&&son>1) cut[u]=1;//树根，割点 if(u==pre) add_block[u]=son-1; instack[u]=0; top--; } int init()//初始化 { cnt=tot=top=bridge=0; memset(h,-1,sizeof(h)); memset(instack,0,sizeof(instack)); memset(cut,0,sizeof(cut)); memset(add_block,0,sizeof(add_block)); memset(dfn,0,sizeof(dfn)); }
题目：poj 1523
题意：求出割点，并输出删除割点后有几个连通块
直接带上面代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<queue> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=10010; const int maxm=200100; struct node{ int u,v,nxt; bool cut;//记录是否是桥 }e[maxm]; int h[maxn],cnt; int low[maxn],dfn[maxn],st[maxn],tot,top; bool instack[maxn]; bool cut[maxn];//记录是否是割点 int add_block[maxn];//删除一个点后增加的连通块 int bridge;//记录桥的条数 void add(int u,int v) { e[cnt].u=u;e[cnt].v=v;e[cnt].cut=0; e[cnt].nxt=h[u];h[u]=cnt++; } void tarjan(int u,int pre) { low[u]=dfn[u]=++tot; st[top++]=u; instack[u]=1; int son=0; int pre_cnt=0;//处理重边 for(int i=h[u];i!=-1;i=e[i].nxt) { int v=e[i].v; if(v==pre&&pre_cnt==0) { pre_cnt++; continue; } if(!dfn[v]) { son++; tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>dfn[u])//桥 { bridge++; e[i].cut=1; e[i^1].cut=1; } if(u!=pre&&low[v]>=dfn[u])//非树根，割点 { cut[u]=1; add_block[u]++; } } else low[u]=min(low[u],dfn[v]); } if(u==pre&&son>1) cut[u]=1;//树根，割点 if(u==pre) add_block[u]=son-1; instack[u]=0; top--; } int ans,n,m; int main() { int a,b; int k=0; while(scanf("%d",&a)!=EOF) { cnt=tot=ans=n=0; memset(h,-1,sizeof(h)); memset(add_block,0,sizeof(add_block)); memset(dfn,0,sizeof(dfn)); memset(cut,0,sizeof(cut)); if(!a) break; scanf("%d",&b); add(a,b); add(b,a); n=max(n,max(a,b)); while(scanf("%d",&a)!=EOF) { if(!a) break; scanf("%d",&b); add(a,b); add(b,a); n=max(n,max(a,b)); } tarjan(n,n); for(int i=1;i<=n;i++) if(cut[i]) ans++; printf("Network #%d ",++k); if(!ans) printf(" No SPF nodes "); else { for(int i=1;i<=n;i++) if(cut[i]) printf(" SPF node %d leaves %d subnets ",i,add_block[i]+1); } printf(" "); } return 0; }
题目：zoj 2588
题意： 求有重边无向图中的桥的个数，并输出
代码：
/* 1.可以求出图的割点和桥 2.可以求删除每个点后增加的连通块 */ #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<queue> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=10010; const int maxm=200100; struct node{ int u,v,nxt; bool cut;//记录是否是桥 }e[maxm]; int h[maxn],cnt; int low[maxn],dfn[maxn],st[maxn],tot,top; bool instack[maxn]; bool cut[maxn];//记录是否是割点 int add_block[maxn];//删除一个点后增加的连通块 int bridge;//记录桥的条数 void add(int u,int v) { e[cnt].u=u;e[cnt].v=v;e[cnt].cut=0; e[cnt].nxt=h[u];h[u]=cnt++; } void tarjan(int u,int pre) { low[u]=dfn[u]=++tot; st[top++]=u; instack[u]=1; int son=0; int pre_cnt=0;//处理重边 for(int i=h[u];i!=-1;i=e[i].nxt) { int v=e[i].v; if(v==pre&&pre_cnt==0) { pre_cnt++; continue; } if(!dfn[v]) { son++; tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>dfn[u])//桥 { bridge++; e[i].cut=1; e[i^1].cut=1; } if(u!=pre&&low[v]>=dfn[u])//非树根，割点 { cut[u]=1; add_block[u]++; } } else low[u]=min(low[u],dfn[v]); } if(u==pre&&son>1) cut[u]=1;//树根，割点 if(u==pre) add_block[u]=son-1; instack[u]=0; top--; } int init()//初始化 { cnt=tot=top=bridge=0; memset(h,-1,sizeof(h)); memset(instack,0,sizeof(instack)); memset(cut,0,sizeof(cut)); memset(add_block,0,sizeof(add_block)); memset(dfn,0,sizeof(dfn)); } int n,m; int ans[maxm];//记录答案 int main() { int t; scanf("%d",&t); while(t--) { init(); scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,i); int num=0; for(int i=0;i<cnt;i+=2) { if(e[i].cut) ans[num++]=i/2+1; } printf("%d ",bridge); for(int i=0;i<num;i++) { if(i!=num-1) printf("%d ",ans[i]); else printf("%d ",ans[i]); } if(t) printf(" "); } return 0; }