题意：给出一张图求它的割点个数：
割点:
定义：无向图中，如果有一个顶点，删除这个顶点以及这个顶点相关联的边以后，图的连通分量增多，就称这个点集为割点。
判断一个顶点是不是割点除了从定义，还可以从DFS（深度优先遍历）的角度出发。我们先通过DFS定义两个概念。
假设DFS中我们从顶点U访问到了顶点V（此时顶点V还未被访问过），那么我们称顶点U为顶点V的父顶点，V为U的孩子顶点。
在顶点U之前被访问过的顶点，我们就称之为U的祖先顶点。
显然如果顶点U的所有孩子顶点可以不通过父顶点U而访问到U的祖先顶点，那么说明此时去掉顶点U不影响图的连通性，U就不是割点。
相反，如果顶点U至少存在一个孩子顶点，必须通过父顶点U才能访问到U的祖先顶点，那么去掉顶点U后，顶点U的祖先顶点和孩子顶点就不连通了，说明U是一个割点。
情况1：1.u为当前搜索树的根结点且u的子树数量大于1 即 (x==f&&son>=2)
情况2：2.u不为根且存在树边(u,v)使dfn(u)<=low(v) 对应(low[v] >= dfn[x] && x != f)
完整代码：
#include <cstdio> #include <stack> #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int maxn = 1e3+5; const int maxm = 1e6+5; struct Edge{ int v,next; int u; }edge[maxm]; int ans ; int n,a,b; int head[maxn]; int top,num; int dfn[maxn],low[maxn]; int cut[maxn];//标记是否为割点 int id; void tarjan(int x,int f){//当前结点以及父节点 //(1)结点u初值 low[x] = dfn[x] = ++id; //定义根结点孩子个数 int son = 0; //(2)枚举每一条边 for(int i = head[x]; ~i;i= edge[i].next){ //(3)入过结点u为强连通分量的根节点时 int v = edge[i].v; //(4)没有被访问时候递归搜索 if(!dfn[v]){ tarjan(v,x); low[x] = min(low[x],low[v]); //(5)如果该子节点不能到达祖先节点 (标记) if(low[v] >= dfn[x] && x != f) cut[x] = 1;
//每从根结点往孩子走就加1 if(x == f) son++; } low[x] = min(low[x],dfn[v]); } //(6)根节点且孩子个数大于2即为割点 if(x == f && son >= 2) cut[x] = 1; } void add(int u,int v){ edge[top].v = v; edge[top].next = head[u]; head[u] = top++; } void init(){ memset(head,-1,sizeof(head)); memset(cut,0,sizeof(cut)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); id = ans = top = 0; } int main(){ while(~scanf("%d",&n) &&n){ init(); while(scanf("%d",&a) &&a){ char ch; while(scanf("%d%c",&b,&ch)){ add(a,b),add(b,a); if(ch == ' ') break; } } for(int i = 1;i<=n;i++){ if(!dfn[i]) tarjan(i,i); } for(int i = 1;i<=n;i++){ if(cut[i]) ans++; } printf("%d ",ans); } return 0; }