欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

割点和桥

程序员文章站 2022-04-15 12:41:15
...

算法大概:

dfn[v]记录的是节点v被访问的深度,low[v]记录的是点v可以到达的访问时间最早的祖先

在深度遍历图的过程中,记录下每个节点的深度,对当前节点u,以及和它相连的节点v,有两种情况。

(1).v没被访问过,这是递归访问节点v,并用i的可以到达的最早祖先来更新u的low值。

(2).v被访问过,这时说明有一个环,用v的深度来更新u的low值。

u是割点的条件:u是根且有大于一个的儿子,或者u不是根,且u有一个儿子v使得low[v]>=dfn[u]。

(u,v)是桥的条件:low[v]>dfn[u]

附上代码:


#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+5;
const int maxm=2e5+5;

struct edge{
    int u,v,next;
};
edge edges[maxm];
int head[maxn],tot;

void init()
{
    memset(head,-1,sizeof(head));
    tot=0;
}

void add_edges(int u,int v)
{
    edges[tot].u=u;
    edges[tot].v=v;
    edges[tot].next=head[u];
    head[u]=tot++;
}

int n,m,dfn[maxn],low[maxn],t;
bool cut[maxn],brige[maxm];

void dfs(int u,int f)
{
    dfn[u]=low[u]=t++;
    int child=0;
    for(int i=head[u];~i;i=edges[i].next){
        int v=edges[i].v;
        if(!dfn[v]){
            dfs(v,u);
            child++;
            low[u]=min(low[u],low[v]);
            if((f==-1&&child>1)||(f!=-1&&low[v]>=dfn[u])){
                cut[u]=true;
            }
            if(low[v]>dfn[u]){
                brige[i]=true;
            }
        }else if(v!=f){
            low[u]=min(low[u],dfn[v]);
        }
    }
}

int main()
{
    init();
    scanf("%d%d",&n,&m);
    int a,b;
    for(int i=0;i<m;i++){
        scanf("%d%d",&a,&b);
        add_edges(a,b);
        add_edges(b,a);
    }
    t=1;
    dfs(0,-1);
    for(int i=0;i<n;i++){
        if(cut[i]){
            cout<<i<<endl;
        }
    }
    for(int i=0;i<tot;i++){
        if(brige[i]){
            printf("%d %d\n",edges[i].u,edges[i].v);
        }
    }
    return 0;
}