题面
1524
一句话题意：求桥的数量。
思路
正常的求桥的思路。可以看我的其他文章，亦可以在这里随便看一看我随便写的。
首先，求桥要用Tarjin，所以dfn和low数组还是要有的。
然后是判断一条边是桥的条件：当一条边是树枝边（即从父亲k到儿子p去的边），然后low[p]>=dfn[k]，即p不通过k而能到达的最小值（即从p的子树走）比k要大，那么这条边就是桥。（很简单是不是）
所以代码就这么出来了。
//连栈、co数组、num……都没用到
void tarjin(int k,int fa)
{
low[k]=dfn[k]=++tot;
for(int i=head[k]; i; i=a[i].nxt)
if(a[i].to==fa) continue;
else if(!dfn[a[i].to])
{
tarjin(a[i].to,k),low[k]=min(low[k],low[a[i].to]);
if(low[a[i].to]>dfn[k]) ans++;
}
else low[k]=min(low[k],dfn[a[i].to]);
}
代码
直接上代码（重点来了）
#include <bits/stdc++.h>
using namespace std;
int n,m,x,y,ans;
int head[30005],cnt;
int dfn[30005],low[30005],tot;
struct node
{
int to,nxt,p;
} a[60005];
void add(int x,int y)
{
a[++cnt].to=y,a[cnt].nxt=head[x],head[x]=cnt;
}
void tarjin(int k,int fa)
{
low[k]=dfn[k]=++tot;
for(int i=head[k]; i; i=a[i].nxt)
if(a[i].to==fa) continue;
else if(!dfn[a[i].to])
{
tarjin(a[i].to,k),low[k]=min(low[k],low[a[i].to]);
if(low[a[i].to]>dfn[k]) ans++;
}
else low[k]=min(low[k],dfn[a[i].to]);
}
int main()
{
scanf("%d%d",&n,&m);
while(n!=0&&m!=0)
{
memset(dfn,0,sizeof(dfn)),memset(low,0,sizeof(low)),memset(head,0,sizeof(head)),ans=tot=cnt=0;
for(int i=1; i<=m; i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
tarjin(1,0),printf("%d\n",ans),scanf("%d%d",&n,&m);
}
return 0;
}
小结
这道题虽然是一道非常模板的求桥的题目，so随便写一写代码就能过了但是我调了很久，因此代码能力太弱了（主要是判断fa的语句放错地方了）
有问题可以先看我的另外一篇文章，也欢迎私信我。
完结撒花！！！
别忘了点赞，关注，谢谢！！
