BCC.cpp

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)

#define MAX_V 100000
vector<int> G[MAX_V];
void visit(int cur, int prev, vector<pii> &brg, vector<vector<int>> &each_bcc, vector<int> &cmp, stack<int> &roots, stack<int> &S, vector<bool> &inS, vector<int> &order, int &k){
    order[cur] = ++k;                //頂点を訪れた順に順序付け
    S.push(cur); inS[cur] = true;    //訪れた頂点の集合を管理
    roots.push(cur);                //各二重辺連結成分をDFS木の部分木として見たときの、根を管理
    
    rep(i,G[cur].size()){
        int to = G[cur][i];
        if(order[to]==0){
            visit(to,cur,brg,each_bcc,cmp,roots,S,inS,order,k);
        }
        else if(to!=prev && inS[to]){    //後退辺をたどる
            while(order[roots.top()] > order[to]) roots.pop();    //cur〜toまで(toは含まない)の頂点をrootsから捨てる
        }
    }
    
    if(cur==roots.top()){    //オイラーツアーみたいなのを考えて、葉側から根側に橋を渡るとき、条件式がTRUEになる
        if(prev!=-1)brg.pb(pii(prev,cur));
        vector<int> bcc;
        while(1){
            int node = S.top(); S.pop(); inS[node] = false;    //集合Sからnodeを捨てる
            bcc.pb(node);                                    //nodeを二重辺連結成分に追加
            cmp[node] = each_bcc.size();
            if(node==cur)break;
        }
        each_bcc.pb(bcc);
        roots.pop();
    }
}


void bridge(int V, vector<pii> &brg, vector<vector<int>> &each_bcc){
	vector<int> order(V);
	vector<bool> inS(V);
	stack<int> roots, S;
	int k=0;
	rep(i,V){
		if(order[i]==0){
			visit(i,-1,brg,each_bcc,roots,S,inS,order,k);
		}
	}
}