強連結成分分解 LIB::StronglyConnectedComponents

互いに行き来できる頂点集合に分解する　 $O(V+E)$
https://manabitimes.jp/math/1250

メンバ関数

StronglyConnectedComponents(G& g);

コンストラクタ

vector<set<ll>> Run(bool ignore_dag);

ignore_dag=false にすると閉路を持たない各頂点はサイズ1の各集合に割り当てる
（このモードではDAG含め全ての頂点を返すが、自己ループの区別は出来ない）
ignore_dag=true にすると閉路を持たない頂点を処理結果に含めない
（このモードではDAGの頂点を返さないが、自己ループの検出が出来るようになる）

ソースコード

namespace LIB{
	template<class G>struct StronglyConnectedComponents{
		using ll = long long;
		G& g;
		StronglyConnectedComponents(G& g):g(g){}

		vector<set<ll>> Run(bool ignore_dag){
			// トポロジカルソート
			vector<ll> tnd; // トポロジカルに並べ直した頂点集合
			vector<ll> cnt(g.size());
			auto dfs=[&](auto self, ll i)->void{
				cnt[i]++;
				for (auto& [j,c]:g[i]){
					if(cnt[j]) continue;
					self(self,j);
				}
				tnd.push_back(i);
			};
			for (ll i=0;i<(ll)g.size();i++){
				if(cnt[i]) continue;
				dfs(dfs,i);
			}
			// 逆順dfs
			fill(cnt.begin(),cnt.end(),false);
			vector<ll> ideg(g.size()); // 入次数
			vector<ll> odeg(g.size()); // 出次数
			G rg(g.size()); // 辺を逆向きにしたグラフ
			for(ll i=0;i<(ll)g.size();i++){
				if ((ll)g[i].size()!=0) odeg[i]++;
				for (auto& [j,c]:g[i]) rg[j].push_back({i,1}),ideg[j]++;
			}
			auto rdfs = [&](auto self, ll i, auto& cnd)->void{
				cnt[i]++;
				cnd.back().insert(i);
				for (auto& [j,c]:rg[i]){
					if(cnt[j]) continue;
					self(self,j,cnd);
				}
			};
			vector<set<ll>> cnd; // cyclic node
			for(ll i=(ll)tnd.size()-1;0<=i;i--){
				if(ideg[tnd[i]]==0&&odeg[tnd[i]]==0) continue;
				if(cnt[tnd[i]]==1) continue;
				cnd.resize(cnd.size()+1),rdfs(rdfs,tnd[i],cnd);
			}
			// 自己ループの処理
			vector<set<ll>> res;
			if(ignore_dag) {
				for(auto& e:cnd)if(e.size()!=1) res.push_back(e);
				for(ll i=0;i<(ll)g.size();i++)for(auto& [j,c]:g[i])if(i==j) res.resize(res.size()+1),res.back().insert(j);
			} else res=cnd;
			return res;
		}
	};
}