双连通分量 之 一本通1524:旅游航道

题面

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的语句放错地方了)
有问题可以先看我的另外一篇文章,也欢迎私信我。


完结撒花!!!
别忘了点赞关注,谢谢!!

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容