HIHO #1184 : 连通性二·边的双连通分量

本文主要是介绍HIHO #1184 : 连通性二·边的双连通分量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

Tarjan算法，介绍可以看题目讲解，很好很清楚

无向图边的双联通分量的定义：对于一个无向图的子图，当删除其中任意一条边后，不改变图内点的连通性，这样的子图叫做边的双连通子图。而当子图的边数达到最大时，叫做边的双连通分量。

或者说，对于一个连通图，如果任意两点至少存在两条”边不重复”的路径。也就是要去每条边至少在一个简单的环中，也就是说所有的边都不是桥

同样是2个方法：
1）题目伪代码实现
2）优化版

#include<bits/stdc++.h>
using namespace std;
#define cl(a,b) memset(a,b,sizeof(a))
#define LL long long
#define pb push_back
#define gcd __gcd#define For(i,j,k) for(int i=(j);i<k;i++)
#define lowbit(i) (i&(-i))
#define _(x) printf("%d\n",x)const int maxn = 2e4+2000;
const int inf  = 1 << 28;int n,m;
vector<int> G[maxn];int fa[maxn],low[maxn],dfn[maxn],stk[maxn];
bool vis[maxn];
int top,counter;int cnt;
int ans[maxn];
int belong[maxn];void dfs(int u){vis[u]=true;dfn[u]=low[u]=++counter;stk[top++]=u;for(int i=0;i<G[u].size();i++){int v = G[u][i];if(!vis[v]){fa[v]=u;dfs(v);low[u]=min(low[u],low[v]);}else if(v!=fa[u]){low[u]=min(low[u],dfn[v]);}}if(low[u]==dfn[u]){do{int x = stk[--top];belong[x] = cnt;if(ans[cnt]==0)ans[cnt]=x;ans[cnt]=min(ans[cnt],x);}while(stk[top]!=u);cnt++;}
}void init(int n){top = counter = cnt = 0;for(int i=0;i<=n;i++){fa[i]=-1;vis[i]=dfn[i]=low[i]=0;G[i].clear();}
}int main(){cin>>n>>m;init(n);for(int i=0;i<m;i++){int x,y;cin>>x>>y;G[x].pb(y);G[y].pb(x);}dfs(1);cout<<cnt<<endl;for(int i=1;i<=n;i++){if(i==1)cout<<ans[belong[i]];else cout<<' '<<ans[belong[i]];}cout<<endl;return 0;
}

2）

#include<bits/stdc++.h>
using namespace std;
#define cl(a,b) memset(a,b,sizeof(a))
#define LL long long
#define pb push_back
#define gcd __gcd#define For(i,j,k) for(int i=(j);i<k;i++)
#define lowbit(i) (i&(-i))
#define _(x) printf("%d\n",x)const int maxn = 2e4+2000;
const int inf  = 1 << 28;int n,m;
vector<int> G[maxn];int low[maxn],dfn[maxn],stk[maxn];
int top,counter;int cnt;
int ans[maxn];
int belong[maxn];void dfs(int u,int fa){dfn[u]=low[u]=++counter;stk[top++]=u;for(int i=0;i<G[u].size();i++){int v = G[u][i];if(v==fa)continue;if(!dfn[v]){dfs(v,u);low[u]=min(low[u],low[v]);}else{low[u]=min(low[u],dfn[v]);}}if(low[u]==dfn[u]){do{int x = stk[--top];belong[x] = cnt;if(ans[cnt]==0)ans[cnt]=x;ans[cnt]=min(ans[cnt],x);}while(stk[top]!=u);cnt++;}
}void init(int n){top = counter = cnt = 0;for(int i=0;i<=n;i++){dfn[i]=low[i]=0;G[i].clear();}
}int main(){cin>>n>>m;init(n);for(int i=0;i<m;i++){int x,y;cin>>x>>y;G[x].pb(y);G[y].pb(x);}dfs(1,1);cout<<cnt<<endl;for(int i=1;i<=n;i++){if(i==1)cout<<ans[belong[i]];else cout<<' '<<ans[belong[i]];}cout<<endl;return 0;
}