UVA 796 Critical Links(Tarjan求桥)

题目是PDF就没截图了

这题似乎没有重边,若有重边的话这两点任意一条边都不是桥,跟求割点类似的原理

代码:

#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
typedef pair<int,int> pii;
typedef long long LL;
const double PI=acos(-1.0);
const int N=1e6+7;
struct edge
{
int to;
int pre;
};
edge E[N<<1];
int head[N],tot;
int low[N],dfn[N],ins[N],ts,top,st[N];
vector<pii>ans; void init()
{
CLR(head,-1);
tot=0;
CLR(low,0);
CLR(dfn,0);
CLR(ins,0);
ts=top=0;
ans.clear();
}
inline void add(int s,int t)
{
E[tot].to=t;
E[tot].pre=head[s];
head[s]=tot++;
}
void Tarjan(int u,int pre)
{
low[u]=dfn[u]=++ts;
ins[u]=1;
st[top++]=u;
int v;
for (int i=head[u]; ~i; i=E[i].pre)
{
v=E[i].to;
if(v==pre)
continue;
if(!dfn[v])
{
Tarjan(v,u);
low[u]=min<int>(low[u],low[v]);
if(low[v]>dfn[u])
{
pii temp=pii(u,v);
if(temp.first>temp.second)
swap(temp.first,temp.second);
ans.push_back(temp);
}
}
else if(ins[v])
low[u]=min<int>(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
do
{
v=st[--top];
ins[v]=0;
}while (u!=v);
}
}
int main(void)
{
int n,u,v,k,i;
while (~scanf("%d",&n))
{
init();
for (i=0; i<n; ++i)
{
scanf("%d (%d)",&u,&k);
while (k--)
{
scanf("%d",&v);
add(u,v);
add(v,u);
}
}
for (i=0; i<n; ++i)
{
if(!dfn[i])
Tarjan(i,-1);
}
sort(ans.begin(),ans.end());
int SZ=(int)ans.size();
printf("%d critical links\n",SZ);
for (i=0; i<SZ; ++i)
printf("%d - %d\n",ans[i].first,ans[i].second);
putchar('\n');
}
return 0;
}
上一篇:uva 796 Critical Links(无向图求桥)


下一篇:UVA 796 - Critical Links 无向图字典序输出桥