代码
#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
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/344456
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!