UVA 796 Critical Links(模板题)(无向图求桥)

<题目链接>

题目大意:

无向连通图求桥,并将桥按顺序输出。

解题分析;

无向图求桥的模板题,下面用了kuangbin的模板。

 #include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
const int N = 1e4+;
const int M = 1e5+;
struct Edge{
int to,next;
bool cut;//是否为桥的标记
}edge[M];
int head[N],tot,n;
int low[N],dfn[N],Stack[N];
int Index,top;
bool Instack[N],cut[N];
int add_block[N];//删除一个点后增加的连通块
int bridge;
void init(){
memset(head,-,sizeof(head));
memset(dfn,,sizeof(dfn));
memset(Instack,false,sizeof(Instack));
memset(add_block,,sizeof(add_block));
memset(cut,false,sizeof(cut));
Index=top=bridge=tot = ;
}
void addedge(int u,int v){
edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut = false;
head[u] = tot++;
}
void Tarjan(int u,int pre){
low[u] = dfn[u] = ++Index;
Stack[top++] = u;
Instack[u] = true;
int son = ;
for(int i = head[u];i != -;i = edge[i].next){
int v = edge[i].to;
if(v == pre)continue;
if( !dfn[v] ){
son++;
Tarjan(v,u);
if(low[u] > low[v])low[u] = low[v];
if(low[v] > dfn[u]){ //一条无向边(u,v)是桥,当且仅当(u,v)为树枝边,且满足DFS(u)<low(v)
bridge++;
edge[i].cut = true; //正反两边都标记为桥
edge[i^].cut = true;
}
if(u != pre && low[v] >= dfn[u]){
cut[u] = true; //该点为割点
add_block[u]++;
}
}
else if( low[u] > dfn[v])low[u] = dfn[v];
}
if(u == pre && son > )cut[u] = true; //若u为根,且分支数>1,则u割点
if(u == pre)add_block[u] = son - ;
Instack[u] = false;
top--;
}
void solve(){
for(int i = ;i <= n;i++)
if( !dfn[i] )
Tarjan(i,i);
printf("%d critical links\n",bridge); vector<pair<int,int> >ans; /*-- 将桥按顺序输出 --*/
for(int u = ;u <= n;u++)
for(int i = head[u];i != -;i = edge[i].next)
if(edge[i].cut && edge[i].to > u){
ans.push_back(make_pair(u,edge[i].to));
}
sort(ans.begin(),ans.end());
for(int i = ;i < ans.size();i++)
printf("%d - %d\n",ans[i].first-,ans[i].second-);
printf("\n");
}
//处理重边
/*map<int,int>mapit;
inline bool isHash(int u,int v)
{
if(mapit[u*N+v])return true;
if(mapit[v*N+u])return true;
mapit[u*N+v] = mapit[v*N+u] = 1;
return false;
}*/
int main(){
while(scanf("%d",&n) == ){
init();
int u,k,v;
//mapit.clear();
for(int i = ;i <= n;i++){
scanf("%d (%d)",&u,&k);
u++;
//这样加边,要保证正边和反边是相邻的,建无向图
while(k--){
scanf("%d",&v);
v++;
if(v <= u)continue;
//if(isHash(u,v))continue;
addedge(u,v);
addedge(v,u);
}
}
solve();
}
return ;
}

2018-10-18

上一篇:UVA 796 Critical Links(无向图求桥)


下一篇:UVA 796 Critical Links —— (求割边(桥))