学习的这一篇:https://www.byvoid.com/blog/biconnect

割顶:对于无向图G,如果删除某个点u后,连通分量数目增加,称u为图的关节点或者割顶

u为割顶的条件:

(1)u不为树根,以u的任一子节点为根的子树中没有一个点有返回u的祖先的反向边(返祖边)

(2)u为树根,且u有多于一个子树

紫书上有证明

即为,祖先与每一棵子树之间都有返祖边的话(即,删除u点之后,以v为根的整棵子树都可以通过这条返祖边连回到f),该点不是割顶,如果祖先与它的其中一棵子树缺少返祖边的话,那么这个点就是割顶

实现过程

(1)先链式前向星建图

(2)dfs

(3)定义dfn(u)为u在搜索中遍历到的序号      定义low(u)为u或u的子树能通过非父子边追溯到的最早的节点

low(u)=min{dfn(u),

dfn(v)//(u,v)为返祖边,等价于dfn(v)<dfn(u),且v不是u的父亲节点

low(v)//(u,v)为树枝边(父子边)}

(4)当dfn(u)<=low(v)的时候,u为割顶

代码学习的这一篇

http://www.cnblogs.com/naturepengchen/articles/4053890.html

 #include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<algorithm>
using namespace std; #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i) typedef long long LL;
const int INF = (<<)-;
const int mod=;
const int maxn=; int first[maxn],next[maxn],ver[maxn];
int ecnt,tot;
int low[maxn],iscut[maxn],dfn[maxn]; void dfs(int p,int pre){
low[p]=dfn[p]=++tot;
int son=; for(int i=first[p];i!=-;i=next[i]){
int v=ver[i];
if(!dfn[v]){
++son;
dfs(v,p);
low[p]=min(low[p],low[v]);
if(low[v]>=dfn[p]) iscut[p]=;
} else if(dfn[v]<dfn[p]&&v!=pre) {//用返祖边更新low函数
low[p]=min(low[p],dfn[v]);
}
}
if(pre<&&son==) iscut[p]=;
} void addedges(int u,int v){
next[++ecnt]=first[u];
ver[ecnt]=v;
first[u]=ecnt;
} void init(){
memset(low,,sizeof(low));
memset(dfn,,sizeof(dfn));
memset(iscut,,sizeof(iscut));
memset(first,-,sizeof(first)); ecnt=;tot=;
} int main(){
int a,b,n;
char c;
while(scanf("%d",&n)!=EOF&&n){
init();
while(scanf("%d",&a)!=EOF&&a){
while(scanf("%d%c",&b,&c)!=EOF){
addedges(a,b);
addedges(b,a);
if(c=='\n') break;
}
}
dfs(,-);
int ans=;
for(int i=;i<=n;i++)
ans+=iscut[i]; printf("%d\n",ans);
}
return ;
}
05-11 21:51