在无向图中，如果去掉一个点和它所连的边后，图的连通分量增加了，那么我们把这个点叫做割点。 割点有这几个性质： 一个割点属于多个点连通分量。 重要的是这两个：把图强行看成一棵树。 如果u为割点，当且仅当满足下面的1/2 1、如果u为树根，那么u必须有多于1棵子树 2、如果u不为树根，那么（u,v）为树枝边，当Low[v]>=DFN[u]时。也就是v不能连回u的祖先。 所以我们根据这两个性质来判断割点。 代码：
解释：所有iscut初值都是0，除了根是-1，这样就保证需要加两次才能让根为正，最后所有iscut大于0的都是割点。 注意！！！因为割点会把这个点所有边都切掉，所以不用考虑重边的情况，但双连通需要考虑重边。
void tarjan(int u,int fa){ dfn[u]=low[u]=++idc; for(int i=head[u];i;i=e[i].next){ int v=e[i].v; if(v==fa)continue; if(!dfn[v]){ tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]){ iscut[u]++; } }else low[u]=min(low[u],dfn[v]); } }额外解释为什么双联通else那一定要用dfn[v]来更新low[u]。 考虑这样一幅图： 假如我们用low【v】来更新low【u】，一种存在的遍历顺序会导致这样一种情况。 节点3的dfn为3，low为1，节点5的dfn为5，low为1，节点4的dfn为4，low为1。 这种情况导致3不被判定为割点。 下面有一道裸题： poj1144传送门：http://poj.org/problem?id=1144 代码如下：
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #define N 1005 #define del(a,b) memset(a,b,sizeof(a)) using namespace std; int n,num,head[N],iscut[N]; struct Edge{ int v,next; }; Edge e[10*N]; void adde(int i,int j){ e[++num].v=j; e[num].next=head[i]; head[i]=num; } int dfn[N],low[N],idc,ans; void tarjan(int u,int fa){ dfn[u]=low[u]=++idc; for(int i=head[u];i;i=e[i].next){ int v=e[i].v; if(v==fa)continue; if(!dfn[v]){ tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]){ iscut[u]++; } }else low[u]=min(low[u],dfn[v]); } } int main(){ while(~scanf("%d",&n)&&n){ del(head,0); del(e,0); del(dfn,0); del(low,0); del(iscut,0); num=0;idc=0;ans=0; int u,v; while(scanf("%d",&u)&&u){ while(getchar()!='\n'){ scanf("%d",&v); adde(u,v); adde(v,u); } } iscut[1]=-1; tarjan(1,-1); for(int i=1;i<=n;i++) if(iscut[i]>0)ans++; printf("%d\n",ans); } return 0; }