[定义]：
在无向连通图中，如果将其中一个点以及所有连接该点的边去掉，图就不再连通，那么这个点就叫做割点。
在无向连通图中，如果将其中一条边去掉，图就不再连通，那么这条边叫桥。
[思想]：
割点：1）当前节点u为树根的时候，这个节点要有至少两棵子树，否则去掉该节点不会有影响。
2）当前节点u不是树根的时候，要满足low[v]>=dfn[u]，注意u是v的父亲 。
这个父亲是自己根据tarjan搜索的先后顺序，让v的父亲是u。
【注意】：我这里说的是树根，不是环的根，一个树只有一个树根。
【注解】：1）v是一个点那么low[v]=dfn[v]，u后面有个点那么u是个割点
2）v所在有一个环那么low[v]=dfn[x] (x是这个环的根)，
dfn[x]>dfn[u]，u后面连接个环，那么u是个割点。（图1）
dfn[x]=dfn[u]，u是一个环的根，没有u，u后面的子节点无法联通
4）dfn[x]
也有可能low[low[u]]=dfn[x]，就是u这个环的根（low[u]=dfn[根]）
在一个dfn[x]更小的环中，这相当于两个只是相连的环合并成一个大环了（图2）
桥：当且仅当无向边（u，v）是树枝边的时候，需要满足dfn(u)
那么u–v之间一定能够有1条或者多条边不能删去，因为他们之间有一部分无环，是桥。
【注意】：是”<"不是“<=”，u是在这个环的根，因为无向图，少了u->v，图依然联通。（图1）
[代码]
#include
#include
#include
using namespace std; struct ss{ int v; int next; }s[105*105]; int head[100]; int dfn[100]; int low[100]; int res[100];//统计割点 int a[100],b[100]; int n,m,cnt,num,sum; void init() { memset(head,-1,sizeof(head)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(res,0,sizeof(res)); cnt=num=sum=0; } void add(int u,int v) { s[cnt].v=v; s[cnt].next=head[u]; head[u]=cnt++; } void Tarjan(int u,int father) { int son=0;//树根的子树 dfn[u]=low[u]=++num; for(int i=head[u];i!=-1;i=s[i].next) { int v=s[i].v; if(!dfn[v]) { son++; Tarjan(v,u);//v的父亲是u low[u]=min(low[u],low[v]); if(u!=father && low[v]>=dfn[u])//u不是树根 res[u]=1; if(low[v]>dfn[u]) { a[sum]=u; b[sum]=v; sum++; } } else if(v!=father) low[u] = min(low[u],dfn[v]); /* 定义了父亲就是定了一个搜索的方向 v!=father是防止往回走,以免两点成环 这个地方与缩点不一样了 可以说无向图就是一个大环 不能用栈将整个环都缩到一点 我们要相连的环的根有不同的dfn[根] 而每个环有相同的dfn[根]用low记录 这样每个环的根都是一个割点 关于如图3 因为是无向图，所以不用将同时出栈的缩成一个点 2->4后直接就4->5->6,保证同一个外环同一个low */ } if(u==father && son>1)//u是树根 res[u]=1; return; } int main() { while(~scanf("%d%d",&n,&m) && n+m) { init(); int u,v; for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } for (int i = 1; i <= n; i++) if (!dfn[i]) Tarjan(i, i); for (int i = 1; i <= n; i++) if(res[i])printf("割点：%d\n",i); printf("桥：%d\n",sum); for (int i = 0; i < sum; i++) printf("%d<->%d\n",a[i],b[i]); } return 0; }
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/228965.html原文链接：https://javaforall.net
