站外类似Tarjon求调

RT,只要求输出边双连通分量数量

#include<bits/stdc++.h>
using namespace std;
int m,n,a,b,ans,low[500000+10],dfn[500000+10],cnt,belong[500000+10];
vector<int>V[500000+10];
stack<int>S;
void tarjon(int u,int f){
    S.push(u);
    dfn[u]=low[u]=++cnt;
    for(int i=0;i<V[u].size();i++){
        int v=V[u][i];
        if(v==f)continue;
        if(!dfn[v]){
            tarjon(v,u);
            low[u]=min(low[u],low[v]);
        }else{
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]&&!belong[S.top()]){
        ans++;
        int pos;
        do{
            pos=S.top();S.pop();
            belong[pos]=ans;
        }while(pos!=u);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        V[a].push_back(b);
        V[b].push_back(a);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])tarjon(i,0);
    cout<<ans<<endl;
}