HIHO #1183 : 连通性一·割边与割点

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

题目链接

使用Tarjan算法计算无向图的割点和桥，提示讲解的也很清晰
需要注意的是，某一个割点可能会被多次计算，所以一般是先记录然后最后统一输出

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 = 2e5+200;
const int inf  = 1 << 28;int n,m;
vector<int> G[maxn];int fa[maxn],low[maxn],dfn[maxn];
bool vis[maxn];
set<int> cut;
set<pair<int,int> > bridge;
int counter;
void dfs(int u) {int child = 0;vis[u] = true;low[u]=dfn[u] = ++counter;for(int i=0; i<G[u].size(); i++) {int v = G[u][i];if(!vis[v]) {child++;fa[v] = u;dfs(v);low[u]=min(low[u],low[v]);if(fa[u]==-1&&child>1) {cut.insert(u);// 可能会被多次计算}if(fa[u]!=-1&&low[v]>=dfn[u]) {cut.insert(u);// 可能多次计算}if(low[v]>dfn[u]) {if(u<v)bridge.insert(make_pair(u,v));elsebridge.insert(make_pair(v,u));}} else if(v!=fa[u]) {low[u]=min(low[u],dfn[v]);}}
}void init(int n) {counter = 0;for(int i=0; i<=n; i++) {fa[i]=-1;vis[i]=dfn[i]=low[i]=0;G[i].clear();}cut.clear();bridge.clear();
}int main() {while(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);if(cut.empty()) {puts("Null");} else {for(set<int>::iterator i=cut.begin(); i!=cut.end(); i++) {if(i==cut.begin()) {cout<<*i;} else cout<<' '<<*i;}cout<<endl;}for(set<pair<int,int> >::iterator i=bridge.begin(); i!=bridge.end(); i++) {cout<<i->first<<' '<<i->second<<endl;}}return 0;
}

dfs加上一个参数，可以去掉vis,fa(parent)数组
搜索开始dfs(1,1)


#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 = 2e5+200;
const int inf  = 1 << 28;int n,m;
vector<int> G[maxn];int low[maxn],dfn[maxn];
set<int> cut;
set<pair<int,int> > bridge;
int counter;
void dfs(int u,int fa) {int child = 0;low[u]=dfn[u] = ++counter;for(int i=0; i<G[u].size(); i++) {int v = G[u][i];if(v==fa)continue;//避免(fa,u)这条树边的第二次访问if(!dfn[v]) {//时间戳刚好可以作为标记，时间戳从1开始child++;dfs(v,u);low[u]=min(low[u],low[v]);//树边更新if(u==fa&&child>1) {cut.insert(u);// 可能会被多次计算}if(u!=fa&&low[v]>=dfn[u]) {cut.insert(u);// 可能多次计算}if(low[v]>dfn[u]) {if(u<v)bridge.insert(make_pair(u,v));elsebridge.insert(make_pair(v,u));}} else {//上面continue语句后，这里就不用判断了low[u]=min(low[u],dfn[v]);//反向边更新}}
}void init(int n) {counter = 0;for(int i=0; i<=n; i++) {dfn[i]=low[i]=0;G[i].clear();}cut.clear();bridge.clear();
}int main() {while(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);if(cut.empty()) {puts("Null");} else {for(set<int>::iterator i=cut.begin(); i!=cut.end(); i++) {if(i==cut.begin()) {cout<<*i;} else cout<<' '<<*i;}cout<<endl;}for(set<pair<int,int> >::iterator i=bridge.begin(); i!=bridge.end(); i++) {cout<<i->first<<' '<<i->second<<endl;}}return 0;
}