求无向图的割点和桥

求无向图的割点

割点(cut vertex),或者称作割顶更为确切。对于联通图,割点就是删除之后使图不在连通的点,桥就是删除之后使图不连通的边。

POJ1144

裸题,解析看后面。

#include
#include
#include
#include
#include
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
const int N = 110;
vectorG[N];
int pre[N];
int low[N];
bool iscut[N];
int dfs_num;
void init(){
    mem(pre,0); mem(low,0);mem(iscut,0);
    for(int i=0;i= pre[u])
                iscut[u] = 1;
            /* if(low[v] > pre[u])
                iscutbridge = 1;
            */
        }
        else if( v != fa)
            low[u] = min(low[u],pre[v]);//利用后代v的反向边更新low
    }
    if(fa< 0 && child == 1) iscut[u] = 0;//就一个后代(共两个节点)
}
int main(){
    int t;
    while(scanf("%d",&t)!=EOF&&t){
        init();
        int n;
        getchar();
        string tmp;
        while(getline(cin,tmp)){
            int l,r;
            stringstream ss(tmp);
            ss>>l;
            if(!l) break;
            while(ss>>r){
                G[l].push_back(r);
                G[r].push_back(l);
            }
        }
        for(int i=1;i<=t;i++){
            if(!pre[i])
                dfs(i,-1);
        }
        int ans = 0;
        for(int i=1;i<=t;i++){
            if(iscut[i])
                ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}


求无向图的桥

tarjan算法里教我们只要 low[v] > pre[u],即v的后代正能连回v自己,那么(u,v)就是桥,但是这种方法并不常用,因为他只能适用于无重边的情况。

对于求割点,我们用两条反向边建立无向图(图1)。

求无向图的割点和桥_第1张图片 图1 求无向图的割点和桥_第2张图片图2

因为一条边我们会处理两次,所以我们在dfs(int u,int fa),这个参数中存入了fa(父节点)用来判断是否是第二次处理了这条边

        else if( v != fa)
            low[u] = min(low[u],pre[v]);//利用后代v的反向边更新low

即这句话。也就保证了一条边不会回头走(回头走但并不会更新low数组)。

但是如果出现了重边。如图2

按照上面的方法我们仍然不去走这些这些反向箭头, 我们就会漏掉了重边,求出了f 到 v1 是桥这一错误结果(显然 f 到 v1因为重边的存在并不是桥)。

因而对于求桥,我们不能再用求割点的方法dfs(int u,int fa),

我们需要走重边,但是不要走同一条边的反向箭头。

解决方法:

我们对所有的边编号,如果发现是同一条边,我们就continue;(解决了不走同一条边的反向箭头)

dfs(int u,int fa),fa的位置不在储存u节点的父亲节点, 而是储存 u 节点的父亲边。

        int id = G[u][i].id;
        if(id == fa) continue;
id为当前边的编号,如果是同一条边,则直接continue;


习题:HDU4738

#include
#include
#include
#include
#include
#include
#define mem(a,x) memset(a,x,sizeof(a))
#define INF 0x3f3f3f3f
using namespace std;
const int N = 1010;
struct node{
    int v,w,id;
    node(int v = 0,int w = 0,int id = 0):v(v),w(w),id(id){};
};
vectorG[N];
int pre[N];
int low[N];
int dfs_num;int ans ;int n,m;
void init(){
    mem(pre,0); mem(low,0);
    for(int i=0;i<=n;i++) G[i].clear();
    dfs_num = 0;ans = INF;
}
int dfs(int u,int fa){
    low[u] = pre[u] = ++dfs_num;
    for(int i=0;i pre[u])
                ans = min(ans,G[u][i].w);
        }
        else
            low[u] = min(low[u],pre[v]);//利用后代v的反向边更新low
    }
}
int main(){
    int t;
    while(scanf("%d%d",&n,&m)!=EOF&& (n || m)){
        int a,b,c;
        init();
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&a,&b,&c);
            G[a].push_back(node(b,c,i));
            G[b].push_back(node(a,c,i));
        }
        int cnt = 0;
        for(int i=1;i<=n;i++){
            if(!pre[i]){
                cnt++;
                dfs(i,0);
            }
        }
        if(cnt > 1) //多于一个联通分量 不用派人
            ans = 0;
        else if(ans == INF) 
            ans = -1;
        else if(ans == 0) // 没有人看守,也需要派一个人去炸桥
            ans = 1;
        printf("%d\n",ans);
    }
    return 0;
}


你可能感兴趣的