从生成树的顺序来说，一个点是否是一个割点有两种情况：
1、该点是根节点并且有两个孩子。
2、该点是一个普通节点，他的孩子不能在不通过该点的情况下回到之前的点。
所以我们需要两个数组，一个num[]数组记录正常情况下每个点被访问到的次序，即时间戳；一个low[]数组记录其不通过父亲节点能到达的最早的点。
割点的判断条件为low[child]>=num[father],割边的判断条件为low[child]>num[father]；
#include <stdio h="">
#include <stdlib h="">
int num[15];
int low[15];
int flag[15];
int count=0;
int e[15][15];
int n,m;
int root;
int inf=999999;
int a,b,c;
int min(int a,int b)
{
if(a>b)return b;
else return a;
}
void dfs(int cur,int father)
{
int child=0;///判断根节点的孩子数，如果为2则根节点就是一个割点
int i;
count++;
num[cur]=count;
low[cur]=count;
for(i=1;i<=n;i++)
{
if(e[cur][i] == 1)
{
if(num[i]==0)///还没有被扩展
{
child++;
dfs(i,cur);
///更新自己的low数组，应该为和其孩子相比能回到的最早的点，即可以
///通过先向下走再通过一条回头边能够到达的最早的点。
low[cur]=min(low[cur],low[i]);
///判断当前点是不是割点，所以判断孩子的low和当前点num的关系。
if(cur!=root&&low[i]>=num[cur])
flag[cur]=1;
if(cur==root && child==2)
flag[cur]=1;
}
else if(i!=father)///
{
///即回头边，选取一条能回到最早的点的边，记录该点的num为其的low
low[cur]=min(low[cur],num[i]);
}
}
}
return;
}
int main()
{
int i,j;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
e[i][j] = inf;
}
for(i=1;i<=m;i++)
{
scanf("%d %d",&a,&b);
e[a][b] = 1;
e[b][a] = 1;
}
root=1;
dfs(1,root);
for(i=1;i<=n;i++)
{
if(flag[i]==1)
printf("%d",i);
}
printf("\nOVER");
getchar();getchar();
return 0;
}
</stdlib></stdio>
转载请注明原文地址: https://ju.6miu.com/read-6138.html
