割点与割边

割边： 割边是图中的一条边，如果删除这条边，将把连通图分离成两个断开的子图。

割点： 割点是指这样一个顶点，如果删除他，图就会被分割成至少两个分离的子图。

求割边算法伪码：

void bridge( int parent, int u ){
    dep[u]= cnt++; low[u]= dep[u];
    for( e= G[u]; e; e= e->next )
    if( dep[e->v]== 0 ){
        bridge( u, e->v );
        if( low[e->v]< low[u] ) low[u]= low[e->v];
        if( low[e->v]> low[u] )
            printf("%d %d is bridge\n", u, e->v );
    }else if( e-> parent && low[u]> low[e->v] )
    low[u]= low[e->v];
}


对于有重边的图，只需对边进行编号，用边编号来表示父链接。

 

ZOJ 2588 是对有重边的图求割边，代码如下：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define N 10010

typedef pair<int,int> PAIR;

int n, m;
int low[N], dep[N], ans[N], cnt, num;
vector<PAIR> map[N];

void dfs( int road, int u ){
    low[u]= cnt++; dep[u]= low[u];
    
    for( int i= 0; i< map[u].size(); ++i ){
        int v= map[u][i].first, r= map[u][i].second;
        
        if( low[v]== 0 ){
            dfs( r, v );
            
            if( low[v]< low[u] ) low[u]= low[v];
            if( low[v]> dep[u] ) ans[num++]= r;
        }
        else if( road && low[v]< low[u] ) low[u]= low[v];
    }
}

int main(){
    int test;
    scanf("%d",&test );
    for( int t= 1; t<= test; ++t ){
        scanf("%d%d",&n,&m);
        
        for( int i= 1; i<= m; ++i ){
            int x, y;
            scanf("%d%d",&x,&y);
            
            map[x].push_back( PAIR(y,i) );
            map[y].push_back( PAIR(x,i) );
        }
        
        cnt= 1; num= 0;
        for( int i= 0; i<= n; ++i ){
            low[i]= 0; dep[i]= 0; }
            
        dfs( -1, 1 );

        sort( ans, ans+ num );
        printf("%d\n", num );
        if( num ){
            printf("%d", ans[0] );
            for( int i= 1; i< num; ++i ) printf(" %d", ans[i] );
            puts("");
        }
        if( t< test ) puts("");
        
        for( int i= 0; i<= n; ++i ) map[i].clear();
    }
    
    return 0;
}

求割点与求割边算法相似，只是注意 DFS 树根为割点的判断。

算法伪码：

void bridge( u ){
    dep[u]= cnt++; low[u]= dep[u]; num= 0;
    for( e= G[u]; e; e= e->next )
    if( dep[e->v]== 0 ){
        bridge( u, e->v ); num++;
        if( low[e->v]< low[u] ) low[u]= low[e->v];
        if( DFS树根 && low[e->v]>= dep[u] ||
            u== DFS树根 && num> 1 )
            printf("%d is articulation point\n", u );
    }else if( low[u]> dep[e->v] )
    low[u]= dep[e->v];
}

POJ 1144 求割点：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>

using namespace std;

#define N 200

int low[N], dep[N], n, cnt, ans, flag[N];
vector<int> map[N];

void dfs( int u ){
    low[u]= cnt++; dep[u]= low[u];
    
    int num= 0;
    for( size_t i= 0; i< map[u].size(); ++i ){
        int v= map[u][i];
        
        if( dep[v]== 0 ){
            dfs( v ); num++;
            
            if( low[v]< low[u] ) low[u]= low[v];
            if( 1 && low[v]>= dep[u]
                || u== 1 && num> 1 ) flag[u]= 1;
        }else if( dep[v]< low[u] ) low[u]= dep[v];
    }
}

int main(){
    while( scanf("%d",&n)!= EOF ){
        if( n== 0 ) return 0;
        
        for( int i= 0; i<= n; ++i ){
            flag[i]= 0; low[i]= 0; dep[i]= 0; map[i].clear(); }
        
        int u, v;
        while( scanf("%d",&u)!= EOF ){
            if( u== 0 ) break;
            while( getchar()!= '\n' ){
                scanf("%d", &v );
                
                map[u].push_back(v);
                map[v].push_back(u);
            }
        }
        cnt= 1; ans= 0; dfs(1);
        
        for( int i= 1; i<= n; ++i )
        if( flag[i] ) ans++;
        
        printf("%d\n", ans );
    }
    
    return 0;
}