无向图中桥的数量求解（Tarjan算法）

尝试教的新代码：

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+5;
vector<pair<int,int>>G[N]; bool brg[N];
int tsp, dfn[N], low[N];
void tarjan(int x, int in_id)
{
	dfn[x]=low[x]=++tsp;
	for(auto i:G[x])if(i.second!=in_id)
	{
		int y=i.first,id=i.second;
		if(dfn[y]==0)
		{
			tarjan(y,id);
			low[x]=min(low[x],low[y]);
			if(dfn[x]<low[y])brg[id]=1;
		}
		else low[x]=min(low[x],dfn[y]);
	}
}
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF && n && m)
	{
		memset(G,0,sizeof(G));
		for(int i=1,x,y;i<=m;i++)
		{
			scanf("%d%d",&x,&y);
			G[x].push_back({y,i});
			G[y].push_back({x,i});
		}
		tsp=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
		memset(brg, 0, sizeof(brg)); 
		for(int i=1;i<=n;i++)if(dfn[i]==0) tarjan(i, 0);

		int ans=0;for(int i=1;i<=m;i++)if(brg[i]==1) ans++;
		printf("%d\n", ans);
	}
	return 0;
}

代码（标程）：

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10,M=1e6+10;
struct edge{int x,y,pre;}a[M];int alen,last[N];bool bridge[M];
void ins(int x,int y){++alen;a[alen]={x,y,last[x]}; last[x]=alen;}
 
int tsp,cnt,low[N],dfn[N];
void tarjan(int x,int in_edge)
{
    dfn[x]=low[x]=++tsp;
    for(int k=last[x];k>0;k=a[k].pre)if(k!=(in_edge^1))
    {
        int y=a[k].y;
        if(dfn[y]==0)
        {
            tarjan(y,k);
            low[x]=min(low[x], low[y]);
            if(dfn[x]<low[y])bridge[k]=bridge[k^1]=true;
        }
        else low[x]=min(low[x], dfn[y]);
    }
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF && n && m)
    {
        alen=1;memset(last,0,sizeof(last));
        for(int i=1,x,y;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            ins(x,y);ins(y,x);
        }
        tsp=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
        memset(bridge,0,sizeof(bridge));
        for(int i=1;i<=n;i++)if(dfn[i]==0)tarjan(i,0);
        int ans=0;for(int i=1;i<=m;i++) if(bridge[i*2])ans++;
        printf("%d\n",ans);
    }
    return 0;
}

20241219尝试教的新代码：

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+5;
vector<pair<int,int>>G[N]; bool brg[N];
int tsp, dfn[N], low[N];
void tarjan(int x, int in_id)
{
	dfn[x]=low[x]=++tsp;
	for(auto i:G[x])if(i.second!=in_id)
	{
		int y=i.first,id=i.second;
		if(dfn[y]==0)
		{
			tarjan(y,id);
			low[x]=min(low[x],low[y]);
			if(dfn[x]<low[y])brg[id]=1;
		}
		else low[x]=min(low[x],dfn[y]);
	}
}
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF && n && m)
	{
		memset(G,0,sizeof(G));
		for(int i=1,x,y;i<=m;i++)
		{
			scanf("%d%d",&x,&y);
			G[x].push_back({y,i});
			G[y].push_back({x,i});
		}
		tsp=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
		memset(brg, 0, sizeof(brg)); 
		for(int i=1;i<=n;i++)if(dfn[i]==0) tarjan(i, 0);

		int ans=0;for(int i=1;i<=m;i++)if(brg[i]==1) ans++;
		printf("%d\n", ans);
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10,M=1e6+10;
struct edge{int x,y,pre;}a[M];int alen,last[N];bool bridge[M];
void ins(int x,int y){++alen;a[alen]=edge{x,y,last[x]}; last[x]=alen;}
int tsp,cnt,low[N],dfn[N];
void tarjan(int x,int in_edge)
{
dfn[x]=low[x]=++tsp;
for(int k=last[x];k>0;k=a[k].pre)if(k!=(in_edge^1))
{
int y=a[k].y;
if(dfn[y]==0)
{
tarjan(y,k);
low[x]=min(low[x], low[y]);
if(dfn[x]<low[y])bridge[k]=bridge[k^1]=True;
}
else low[x]=min(low[x], dfn[y]);
}
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF && n && m)
{
alen=1;memset(last,0,sizeof(last));
for(int i=1,x,y;i<=m;i++)
{
scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
tsp=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
memset(bridge,0,sizeof(bridge));
for(int i=1;i<=n;i++)if(dfn[i]==0)tarjan(i,0);
int ans=0;for(int i=1;i<=m;i++) if(bridge[i*2])ans++;
printf("%d\n",ans);
}
return 0;
}