UVA 796 Critical Links —— (求割边(桥))

  和求割点类似,只要把>=改成>即可。这里想解释一下的是,无向图没有重边,怎么可以使得low[v]=dfn[u]呢?只要它们之间再来一个点即可。

  总感觉图论要很仔细地想啊- -一不小心就弄混了。。

  另外从这题发现,代码还是写成模块化比较好,比如solve一个函数,init一个函数等等,这样可以避免很多东西忘记写,比方说dfn或者G的清空等等。。

  代码如下:

 #include <stdio.h>
#include <stack>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std; const int N = +; stack<int> S;
int scc_cnt;
int dfs_clock;
int dfn[N];
int low[N];
int iscut[N];
vector<int> G[N];
int n; struct bridge
{
int u,v;
void clear()
{
if(this->u > this->v) swap(this->u,this->v);
}
bool operator < (const bridge & A) const
{
return u==A.u ? v<A.v : u<A.u;
}
};
vector<bridge> ans; void dfs(int u,int fa)
{
dfn[u]=low[u]=++dfs_clock;
for(int i=;i<G[u].size();i++)
{
int v = G[u][i];
if(!dfn[v])
{
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])
{
bridge bri = (bridge){u,v};
bri.clear();
ans.push_back(bri);
}
}
else if(dfn[v]<dfn[u] && v!=fa)
{
low[u]=min(low[u],dfn[v]);
}
}
} void init()
{
for(int i=;i<n;i++) G[i].clear();
memset(dfn,,sizeof(dfn));
dfs_clock=;
ans.clear();
} void solve()
{
for(int i=;i<n;i++)
{
if(!dfn[i]) dfs(i,-);
} sort(ans.begin(),ans.end());
printf("%d critical links\n",ans.size());
for(int i=;i<ans.size();i++)
{
printf("%d - %d\n",ans[i].u,ans[i].v);
}
puts("");
} int main()
{
while(scanf("%d",&n)==)
{
init(); for(int i=;i<=n;i++)
{
int u,num;
scanf("%d (%d)",&u,&num); while(num--)
{
int v;
scanf("%d",&v);
G[u].push_back(v);
G[v].push_back(u);
}
}
solve();
}
return ;
}
上一篇:UVA 796 Critical Links(模板题)(无向图求桥)


下一篇:AcWing 906. 区间分组