基准算法求解图论-桥C++代码

下面是一个简单的基准算法求解图论中桥的 C++ 代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=1e6+10;
int n,m,dfn[N],low[N],tim,cnt,vis[N],head[N],ver[M<<1],Next[M<<1],tot;
void add(int x,int y)
{
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void tarjan(int x,int from)
{
    dfn[x]=low[x]=++tim;
    vis[x]=1;
    for(int i=head[x];i;i=Next[i])
    {
        int y=ver[i];
        if(!dfn[y])
        {
            tarjan(y,i),low[x]=min(low[x],low[y]);
            if(dfn[x]<low[y])
            {
                cnt++;
                printf("%d %d\n",x,y);
            }
        }
        else if(i!=(from^1)) low[x]=min(low[x],dfn[y]);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,a,b;i<=m;i++) scanf("%d%d",&a,&b),add(a,b),add(b,a);
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,-1);
    printf("%d\n",cnt);
    return 0;
}

该代码使用了 Tarjan 算法来求解图中的桥，具体实现细节可以参考代码注释。