首页 > 其他 > 详细

无向图的边连通分量/桥

时间:2020-04-25 19:18:10      阅读:59      评论:0      收藏:0      [点我收藏+]

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5010,M=20010;
int h[N],e[M],nex[M],idx,n,m;
int dfn[N],low[N],timestamp,id[N];
int sk[N],top;
int dcc_cnt,d[N];//每个双联通分量的度
bool is_bridge[N];//记录每条边是否是桥
void add(int x,int y){
    e[idx]=y;
    nex[idx]=h[x];
    h[x]=idx++;
}
void tarjan(int u,int from){
    dfn[u]=low[u]=++timestamp;
    sk[top++]=u;
    for(int i=h[u];~i;i=nex[i]){
        int v=e[i];
        if(!dfn[v]){
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<low[v]){
                is_bridge[i]=is_bridge[i^1]=1;
            }
        }
        else if(i!=(from^1)){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        ++dcc_cnt;
        int v;
        do{
            v=sk[--top];
            id[v]=dcc_cnt;
        }while(v!=u);
    }
}
int main(){
    memset(h,-1,sizeof h);
    cin>>n>>m;
    while(m--){
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    tarjan(1,-1);//如果图联通 跑一次即可
}

无向图的边连通分量/桥

原文:https://www.cnblogs.com/jjl0229/p/12774552.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!