D17 Tarjan 割边

参考程序1

/*【参考程序】
割边判定法则:无向图中存在 x的子节点 y，满足:dfn[x] < low[y]，则边(x,y)为割边。 
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=5e5+10;
typedef pair<int,int> PII;
vector<PII> G[N]; bool brg[M];
int tsp,low[N],dfn[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]=true;
        }
        else low[x]=min(low[x],dfn[y]);
    }
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    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);

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

参考程序2

/*【参考程序】
割边判定法则:无向图中存在 x的子节点 y，满足:dfn[x] < low[y]，则边(x,y)为割边。 
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e6+10;
struct edge{int x,y,pre;}a[M*2];int alen,last[N];bool bridge[M*2];
void ins(int x,int y){++alen;a[alen]={x,y,last[x]}; last[x]=alen;}

int tsp,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;scanf("%d%d",&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);
    for(int i=1;i<=m;i++) if(bridge[i*2])printf("%d\n",i);
    return 0;
}