首先，对于单独的一个点，或者2个点，我们不予考虑，因为我们没法认定。
分情况：
如果待确定的点不是搜索树的根节点，那么关键点可以认为是这样的点V，他的子孙节点中存在一个节点P，从P出发继续向下拓展（也就是不再走已经走过的边，而是向下兜圈子，然后通过某个后向边回到前面已经访问过的点，这里可以看出后向边的价值，后向边在dfs中是不允许扩展的，但是我们说的“兜回到祖先”就是通过某个后向边实现的）dfs不能达到V的祖先，事实上，只要有任意一个子孙节点符合这个特性，那么v就是关键点，因为原本子孙和祖先是连通的，删除它之后，他的子孙至少无法走到他的祖先（包括它的兄弟姐妹。。。）
如果是根节点，他如果只有一个子树，那么他不是关键点，如果有多于一个的子树，那么他必然是关键点
具体实现：
具体实现是这样的，我们定义一个点上的函数dfn(v)，表示v这个点在dfs过程中第一次访问的顺序，然后，为了达到上面的定义，我们再定义一个点上的函数low(v)，low(v)表示从v出发，继续向下拓展搜索，所能达到的最早的点，也就是dfn最小的点
显然，low(v)有：
low(v)=min(dfn(v),low(s),dfn(w))
其中，s是所有儿子节点，w是v的后向边
割顶：
连通图G的一个顶点子集V，如果删除这个顶点子集和它所附带的边后，图便不再连通。则称V是G的割顶集。
最小割顶集中顶点的个数，称为G的连通度。连通度等于1时，割顶集中的那个顶点叫做割顶。
注意：完全图的连通度为总顶点数－1；
牵一发而动全身的点称为割点
边连通度：
连通图G的一个边子集E，如果删除边子集的边后，图便不再连通，则称E是G的桥集。
含有最小边数的桥集的边数|E|称为G的边连通度。|E|＝1时，E中的边叫做桥。
注意：规定不连通图的边连通度为0；完全图的边连通度为总顶点数－1；
连通图的两个特征：
1 连通度<=边连通度<=顶点数
2 顶点数大于2的2连通图的充分必要条件是任两个顶点在一个圈上.(没搞明白)
块的概念：
没有割点的连通子图，这个子图中的任何一对顶点之间至少存在两条不相交的路径，或者说要使两个站点同时发生故障
至少两个站点同时发生故障，这种二连通分支称为块．
显然各个块之间的关系有如下两种：
1 互不连接
2 通过割顶连接(割顶可以属于不同的块，也可以两个块公有一个割顶)
引申：无向图寻找块，关键是找割顶．
满足是割顶的条件：
1 如果u不是根，u成为割顶的充要条件：当且仅当存在u的一个儿子顶点s,从s或者s的后代点到u的祖先点之间不存在后向边．
2 如果u是根，则u成为割顶当且仅当它不止有一个儿子点．
怎样求割顶：
引入一个标号函数：
low(u)=min{dfn(u),low(s),dfn(w)}; s是u的一个儿子，(u,w)是后向边
显然low(u)值是u或者u的后代所能追溯到的最早(序号小)的祖先序号．
利用标号函数low，分析求割顶的步骤：
顶点u不为根且为割顶的条件是当且仅当u有一个儿子s，使得low(s)>=dfn(u),即s和s的后代不会追溯到比
u更早的祖先点．
low(u)的计算步骤：
1 low(u)=dfn(u);
//u在dfs过程中首次被访问
2 low(u)=min{low(u),dfn(w)}
//检查后向边(u,w)时
3 low(u)=min{low(u),low(s)}
//u的儿子s的关联边被检查时
注意：对任何顶点u计算low(u)的值是不断修改的，只有当以U为根的dfs子树和后代的low值,dfn值全部出现以后才停止.
连通图G的一个顶点子集V，如果删除这个顶点子集和它所附带的边后，图便不再连通。则称V是G的割顶集。
最小割顶集中顶点的个数，称为G的连通度。连通度等于1时，割顶集中的那个顶点叫做割顶。
注意：完全图的连通度为总顶点数－1；
牵一发而动全身的点称为割点
边连通度：
连通图G的一个边子集E，如果删除边子集的边后，图便不再连通，则称E是G的桥集。
含有最小边数的桥集的边数|E|称为G的边连通度。|E|＝1时，E中的边叫做桥。
注意：规定不连通图的边连通度为0；完全图的边连通度为总顶点数－1；
连通图的两个特征：
1 连通度<=边连通度<=顶点数
2 顶点数大于2的2连通图的充分必要条件是任两个顶点在一个圈上.(没搞明白)
块的概念：
没有割点的连通子图，这个子图中的任何一对顶点之间至少存在两条不相交的路径，或者说要使两个站点同时发生故障
至少两个站点同时发生故障，这种二连通分支称为块．
显然各个块之间的关系有如下两种：
1 互不连接
2 通过割顶连接(割顶可以属于不同的块，也可以两个块公有一个割顶)
引申：无向图寻找块，关键是找割顶．
满足是割顶的条件：
1 如果u不是根，u成为割顶的充要条件：当且仅当存在u的一个儿子顶点s,从s或者s的后代点到u的祖先点之间不存在后向边．
2 如果u是根，则u成为割顶当且仅当它不止有一个儿子点．
怎样求割顶：
引入一个标号函数：
low(u)=min{dfn(u),low(s),dfn(w)}; s是u的一个儿子，(u,w)是后向边
显然low(u)值是u或者u的后代所能追溯到的最早(序号小)的祖先序号．
利用标号函数low，分析求割顶的步骤：
顶点u不为根且为割顶的条件是当且仅当u有一个儿子s，使得low(s)>=dfn(u),即s和s的后代不会追溯到比
u更早的祖先点．
low(u)的计算步骤：
1 low(u)=dfn(u);
//u在dfs过程中首次被访问
2 low(u)=min{low(u),dfn(w)}
//检查后向边(u,w)时
3 low(u)=min{low(u),low(s)}
//u的儿子s的关联边被检查时
注意：对任何顶点u计算low(u)的值是不断修改的，只有当以U为根的dfs子树和后代的low值,dfn值全部出现以后才停止.
＃i nclude <stdio.h>
#define maxn 30
typedef struct
{
int k,l;
}L;
L l[maxn];
int g[maxn][maxn];
int st[maxn];
int n,p,x,i;
int k[maxn];
int len;
int min(int a,int b)
{
return a<b?a:b;
}
void push(int a)
{
p++;
st[p]=a;
}
int pop()
{
return st[p--];
}
void init()
{
memset(l,0,sizeof(l));
p=0;push(1);
i=1;
len=-1;
l[1].k=1;l[1].l=1;
memset(k,-1,sizeof(k));
x=0;
}
bool ink(int a)
{
for(int i=0;i<len;i++){
if(k==a) return true;
}
return false;
}
void algorithm(int v)
{
int u;
for(u=1;u<=n;u++){
if(g[v]>0){
if(l.k==0){
i++;
l.k=i;
l.l=i;
push(u);
algorithm(u);
l[v].l=min(l[v].l,l.l);
if(l.l>=l[v].k){
if(v!=1 && !ink(v)){
len++;
k[len]=v;
}
if(v==1) x++;
while(st[p]!=v){
printf("%d ",pop());
}
}
}
else l[v].l=min(l[v].l,l.k);
}
}
}
int main()
{
algorithm(1);
if(x>1){
len++;
k[len]=1;
}
}
#define maxn 30
typedef struct
{
int k,l;
}L;
L l[maxn];
int g[maxn][maxn];
int st[maxn];
int n,p,x,i;
int k[maxn];
int len;
int min(int a,int b)
{
return a<b?a:b;
}
void push(int a)
{
p++;
st[p]=a;
}
int pop()
{
return st[p--];
}
void init()
{
memset(l,0,sizeof(l));
p=0;push(1);
i=1;
len=-1;
l[1].k=1;l[1].l=1;
memset(k,-1,sizeof(k));
x=0;
}
bool ink(int a)
{
for(int i=0;i<len;i++){
if(k==a) return true;
}
return false;
}
void algorithm(int v)
{
int u;
for(u=1;u<=n;u++){
if(g[v]>0){
if(l.k==0){
i++;
l.k=i;
l.l=i;
push(u);
algorithm(u);
l[v].l=min(l[v].l,l.l);
if(l.l>=l[v].k){
if(v!=1 && !ink(v)){
len++;
k[len]=v;
}
if(v==1) x++;
while(st[p]!=v){
printf("%d ",pop());
}
}
}
else l[v].l=min(l[v].l,l.k);
}
}
}
int main()
{
algorithm(1);
if(x>1){
len++;
k[len]=1;
}
}
评论