割点、割边

大家好，欢迎来到IT知识分享网。

一、割点、割边、双连通分支概念

证明：假设双连通分支C1、C2，且有两个公共点v1、v2，因为双连通分支划分非桥边，所以v1与v2之间至少有两条边，因此假设v1与v2有两条边，如下图：

命题：两个双连通分支之间的一个公共点是割点。

证明：如果公共点不是割点，则将A点去除后，C1与C2仍然连通，因此必然存在u与v使得(u,v)属于E，因此当A存在时，u到A存在路径，A到v存在路径，u和v之间存在一条边，因此(u,v)与C1中任何一条边都在一个简单回路，(u,v)与C2中任何一条边都在一个简单回路，所以C1与C2合并。

命题：割点一定属于至少两个双连通分支。

证明：如果割点属于一个双连通分支，根据双连通分支定义，去掉任何一个点都不会让图不连通，与割点的定义矛盾。

命题：在一个双连通分支中至少要删除两个点才能够使图G不连通。

证明：双连通分支定义。Trivial。

命题：对于根顶点u，u为割点当且仅当u有至少两个儿子。

命题：对于非根顶点u，u为割点当且仅当u只要存在一个子顶点s，s的后裔（注意是后裔，不是真后裔）没有指向u的真祖先的反向边。

点将一个图分成了两部分，设从任一部分的任一点出发对图进行DFS遍历，当遍历递归到割点后，
就进入了图的第二部分。又因为每个点只能visit一次，所以第二部分的点不论怎样遍历再也回不
到第一部分了。当所有点(第二部分中)都被访问完后，才回溯到割点，再继续向上回溯。

在DFS的过程中，记录每个点u在DFS树中的标号n1(放在dep[u]中)，以及该点所能到达的最小顺序
号n2(存在low[u]中)。注意：这个n2在求取时，是递归进行的，从u的子孙们的low值n2与u的祖先
们的dep值n1(此时u祖先的low值还未求出，dep相当于它的low值)中挑出最小的。这就给了u的儿子
们low值比u还小的机会。然而，如果u是割点，那么u孩子们的low值就决然 >= u 了。这也就成了
判断u是割点的方法。

至于割边，可以再判断u是否为割点的同时，顺便判断<u,u儿子i>是否为割边。只要满足low[i]>u
就行了。

另外，对于dfs起点就是一个割点的情况：如果不是割点，那它必然只有一个儿子(其他连接都被
dfs回溯掉了)。它必须是割点，才能保证它的几个儿子不被dfs回溯掉。

注意：想要记录割点u切去后增加的连通分量数目。不能简单的记录u的孩子数，而必须在判断u为
割点成立的地方进行统计。即有多少个证明了u是割点的孩子，它们就是u在切除后生成的新连通
分量。割点u的某些孩子不一定能证明u是割点，因为它可能与比u小的某个点相连，从而使自己的
low值比u还小，这与具体的dfs树有关，即遍历的顺序有关。 可见末尾的一组数据，对同一个图
的描述，由于建树的方式不同，导致3的儿子4，不能证明3是割点。从而使3的孩子数(3) ！= 3造就
的连通分量数2（删除3后，两棵子树成为连通分量）。

针对这点再强调一点：对根节点删掉自己后，就只剩新生的联通分量了。不同于枝节点，还有旧的
连通分量在。

汇总如下：
如果根结点有大于1个的儿子，那么根结点是割点。(这是防止)
如果对于点u的某个儿子v，有low[v] >= dep[u]，那么u就是一个割点。
如果对于点u的某个儿子v，有low[v] > dep[u]，那么(u,v)是一条割边。

 #include<iostream>
#include<algorithm>
using namespace std;

const int N = 110;
const int WHITE = 0,GREY = 1,BLACK = 2; //标记值
int map[N][N];
int col[N],low[N],dep[N];//color
int n,m;
bool tag[N];//标记点i是否割点

//求0-1图的割点
void dfs(int now,int father,int depth){

    col[now] = GREY;
    dep[now] = depth;
    int child = 0;
    for(int i=1;i<=n;i++){

        if(map[now][i]==0)continue;
       
        if(i != father && col[i] == GREY)
            low[now] = min(low[now], dep[i]);//low需要被初始化成大数
        if(col[i] == WHITE){

            dfs(i, now, depth+1);
            child = child + 1;
            low[now] = min(low[now], low[i]);

            if((now==1&&child>1)||(now!=1&&low[i]>=dep[now])) //判割点
                tag[now] = 1;//注意：需要记录该割点增加几个联通分量的操作需要在这里cnt++
        }
    }
    col[now] = BLACK;
}

void init(){

    memset(map,0,sizeof(map));
    memset(col,0,sizeof(col));
    memset(tag,0,sizeof(tag));
    for(int i=0;i<=n;i++)low[i]=INT_MAX; //low应该被初始化成大值
}

int main(){

    int a,b;
    cin>>n>>m;
    init();
    for(int i=0;i<m;i++){

        cin>>a>>b;
        map[a][b] = map[b][a] = 1;//无向图
    }
   
    dfs(1,1,0);//dfs(root,root,0)的形式调用就行了
    int ans=0;
   
    for(int i=1;i<=n;i++)
        if(tag[i])cout<<i<<‘ ‘;
   
    cout<<endl;
    system(“pause”);
    return 0;
}

另外一种写法：

#include <iostream>

 using namespace std; 

const int MAXN = 1010;

 int map[MAXN][MAXN],bridge[MAXN][MAXN]; 

int color[MAXN],d[MAXN],anc[MAXN],cut[MAXN],visited[MAXN];

 int node_for_tree[MAXN],map_for_tree[MAXN][MAXN];

 int N,M,bridgeN,index; 

void DFS(int child,int father,int deep)

{
//在遍历时father先于child，且两者有连边 int i;

  color[child] = 1;//遍历过可是未找到它所属的强连通分量,标志为灰色 

d[child] = deep;//标志找到该节点时是第几层 

anc[child] = deep;#anc[child]等价low[child];

  int nodeN = 0;//标志该强联通分量的节点个数

 for( i = 1 ; i <= N ; i ++ )

{
//枚举所有节点 

if( map[i][child] && i != father && color[i] == 1 )//i已编历，存在回边 

anc[child] = min(anc[child],d[i]);//保存连通分量里度数最小的 

if( map[i][child] && !color[i] )//有连边且未遍历 

{ 

DFS(i,child,deep+1);//递归搜索下一层 

nodeN ++;//将新节点加入连通分量中 

anc[child] = min(anc[child],anc[i]); //如果child是根且不知一个顶点在该连通分量中or child非根且没有回边可到达father的祖先

  if(( child == 1 && nodeN > 1 ) || (child != 1 && anc[i] >= d[child] )) 

cut[child] = 1;//标志为割点 

if( anc[i] > d[child] )//说明只能又child到i了，没有回边 

{

  bridge[child][i] = bridge[i][child] = 1;//标记为桥 bridgeN ++;

}

  }

  }

  color[child] = 2;//遍历完时赋为黑色

} 

void tight(int j)

{ 

visited[j] = 1; 

node_for_tree[j] = index; 

int i;

 for( i = 1 ; i <= N ; i ++ ) 

{

  if( !visited[i] && map[j][i]) 

if( !bridge[j][i] )//非桥 tight(i);

  }

 }

  int main()

{

  int i,j,a,b; 

char str[20]; //freopen(“3352.txt”,”r”,stdin); //

while( gets(str) != NULL ) 

while( scanf(“%d %d”,&N,&M) != EOF ) 

{

  //printf(“Output for “); 

//puts(str);

 memset(map,0,sizeof(map)); 

memset(color,0,sizeof(color));

 memset(d,0,sizeof(d));

 memset(anc,0,sizeof(anc)); 

memset(cut,0,sizeof(cut));

  memset(visited,0,sizeof(visited));

 memset(node_for_tree,0,sizeof(node_for_tree));

 memset(map_for_tree,0,sizeof(map_for_tree));

 memset(bridge,0,sizeof(bridge)); 

//scanf(” %d %d”,&N,&M); 

for( i = 0 ; i < M ; i ++ )

  {

  scanf(“%d %d”,&a,&b); 

map[a][b] = 1;//图是双向的 

map[b][a] = 1;

  } 

//getchar();

 bridgeN = 0; 

DFS(1,1,0);//找出关键边，即桥；为缩图成树做准备 

index = 1;

  bool flag = true;

  while( flag )

  {

  flag = false;

  for( i = 1 ; i <= N ; i ++ )//找到第一个没有访问的顶点 

{

  if( !visited[i] )

  {

  flag = true; break;

  } 

}

 tight(i);//将i所在的连通分量绑定为树的一个节点 

index ++; 

}

  for( i = 1 ; i <= N ; i ++ ) 

for( j = 1 ; j <= N ; j ++ ) 

if( bridge[i][j] )//找到桥边 

{

  int t1 = node_for_tree[i];//找到桥两个端点在树中的编号 

int t2 = node_for_tree[j];

 map_for_tree[t1][t2] = 1; 

map_for_tree[t2][t1] = 1;

  } 

int temp,leaf_num = 0; 

for( i = 1 ; i < index ; i ++ )//树节点数总共为index

  {

  temp = 0;

 for( j = 1 ; j < index ; j ++ )

  {

 if( map_for_tree[i][j] && i != j )//有通路且不是环 

temp ++;

  }

  if( temp == 1 )//说明找到叶子节点了，度数为一 

leaf_num ++;

  } 

printf(“%d\n”,(leaf_num+1)/2); 

//getchar(); 

} 

return 0;

  }

第三种写法：