本文共 2394 字，大约阅读时间需要 7 分钟。
割点： 在连通的无向图中，删除一个点和与它所相连的边，无向图不再连通，说明这个点是割点。
思路: 从一个点开始深搜，当这个点不经过他的父亲节点不能返回到比这个父节点更早的时间戳，说明这个点的父节点是割点。
low[v]>=dfn[u]
注意： 判断割点时分两种情况，如果父节点是根节点的话，至少两个儿子才能形成割点！
割边就是去掉一条边使这个图不连通。
low[v]>dfn[u]；不能经过u->v这条边，所以不能等于low[u] (可以用三角形举例)
/*POJ - 1144 求割点数目*/#include #include #include using namespace std;vector edge[110];int cnt;int dfn[110],low[110],root,flag[111];/*考虑图不连通？*/void Tarjan(int u,int fa){ int child=0; dfn[u]=low[u]=++cnt; for(int i=0; i =dfn[u]&&u!=root)/*!!!大于等于*/ { flag[u]=1;/*儿子回到的最早时间戳大于等于x,x不是根节点*/ } else if(u==root&&child>=2) { /*根节点，至少两个儿子*/ flag[u]=1; } } else if(u!=v)/*!!! v点走过*/ { low[u]=min(low[u],dfn[v]); } } return ;}int main(){ int n; while(~scanf("%d",&n)&&n) { int m,t; char c; root=1; cnt=0; for(int i=0; i<=n; i++) { edge[i].clear(); dfn[i]=0; low[i]=0; flag[i]=0; } while(~scanf("%d",&m)&&m) { while(1) { scanf("%c",&c); if(c=='\n') break; scanf("%d",&t); edge[m].push_back(t); edge[t].push_back(m); // printf("%d <---> %d\n",t,m); } } Tarjan(1,1); int sum=0; for(int i=1; i<=n; i++) if(flag[i]) sum++; printf("%d\n",sum); } return 0;}
/*割边*/#include using namespace std;#define N 1000int n,m,first[N],nex[N],w=1,dfn[N],low[N],flag[N],u[N],v[N],root,index;void Tarjan(int x,int father){ int child=0; index++;/*计算时间戳*/ dfn[x]=low[x]=index; for(int i=first[x];i!=-1;i=nex[i]) { int y=v[i];/* x->y */ if(!dfn[y])/*没有被访问过*/ { Tarjan(y,x); low[x]=min(low[x],low[y]); if(low[y]>dfn[x])/*这条边是不是割边*/ printf("%d %d\n",x,y); } else if(x!=father)/*不通过父节点访问*/ low[x]=min(low[y],dfn[x]);/*在割点中不一样low的值不对*/ } return;}int main(){ index=0; int y,x; scanf("%d%d",&n,&m); memset(flag,0,sizeof(flag)); memset(first,-1,sizeof(first)); for(int i=0;i
转载地址：http://smsl.baihongyu.com/