強連結成分分解 LIB::StronglyConnectedComponents

互いに行き来できる（閉路の）頂点集合に分解する $O(v+e)$
https://manabitimes.jp/math/1250

依存クラス

https://9871225.hatenablog.com/entry/2021/06/27/115154
https://9871225.hatenablog.com/entry/2022/03/02/202403

メンバ関数

コンストラクタ $O(v+e)$

template<class G, class V, class E>struct StronglyConnectedComponents(G& g);

Gはグラフの型、Vは頂点の型、Eは辺の型
例: StronglyConnectedComponents<graph,ll,edge> scc(g)
ただし、Eはpair<ll,ll>形式の型以外の動作は未定義
コンストラクタを呼び出した時点で閉路の連結成分毎に頂点集合に分解する

頂点 vi が属する連結成分を新たな頂点としたときの頂点インデックス $O(\log n)$

ll GroupIndex(ll vi)

頂点 vi が属する連結成分のサイズ $O(\log n)$

ll GroupSize(ll vi)

引数の vi は元グラフの頂点インデックスでもSCC実行後の頂点インデックスでもどちらでも ok

新しい有向グラフを作る $O(v+e)$

G NewGraph()

閉路の連結成分毎にまとめた頂点集合を返す $O(e)$

vec<vec<V>> VertexGroups()

ソースコード

namespace LIB {
    template<class V, class E>struct csr {
        vec<V> start;
        vec<E> elist;
        csr(ll n, const vec<pa<V,E>>& edges):start(n+1),elist(edges.size()) {
            forx(e,edges) start[e.a+1]++;
            fori(i,1,n+1) start[i]+=start[i-1];
            vec<V> counter=start;
            forx(e,edges) elist[counter[e.a]++]=e.b;
        }
    };
    template<class G, class V, class E>struct StronglyConnectedComponents {
		StronglyConnectedComponents(G &g):n(lsz(g)),uf(lsz(g)) {
			fori(vi,0,lsz(g)) forxy(nvi,nex,g[vi]) push(edges,pa<V,E>{vi,{nvi,nex}});
			MakeVertexGroups();
		}
		ll GroupIndex(ll vi) { return uf.Find(vi); }
		ll GroupSize(ll vi) { return uf.Size(vi); }
		G NewGraph() {
			if(lsz(graph)==0) MakeNewGraph();
			return graph;
		}
		vec<vec<V>> VertexGroups() { return groups; }
	private:
		vec<pa<V,E>> edges;
		G graph;
		vec<vec<V>> groups;
		ll n;
		UnionFind uf;
		void MakeVertexGroups() {
			auto ids=GetIDs();
			ll group_num=ids.a;
			vec<ll> counts(group_num);
			forx(x,ids.b) counts[x]++;
			groups.resize(ids.a);
			fori(i,0,group_num) groups[i].reserve(counts[i]);
			fori(i,0,n) groups[ids.b[i]].push_back(i);
		}
		void MakeNewGraph() {
			graph.resize(n);
			forx(vs,groups) fori(i,0,lsz(vs)-1) uf.Union(vs[i],vs[i+1]);
			forx(e,edges) {
				ll vi=e.a;
				auto& [nvi,nex]=e.b;
				if(!uf.Same(vi,nvi)||vi==nvi) push(graph[uf.Find(vi)],E{uf.Find(nvi),nex});
			}
		}
		pa<ll,vel> GetIDs() {
			auto g=csr<V,E>(n,edges);
			ll now_ord=0,group_num=0;
			vec<V> visited,low(n),ord(n,-1),ids(n);
			visited.reserve(n);
			auto dfs=[&](auto self, ll v)->void {
				low[v]=ord[v]=now_ord++;
				push(visited,v);
				fori(i,g.start[v],g.start[v+1]) {
					auto [vj,ey]=g.elist[i];
					if(ord[vj]==-1) {
						self(self,vj);
						low[v]=min(low[v],low[vj]);
					} else low[v]=min(low[v],ord[vj]);
				}
				if(low[v]==ord[v]) {
					while(true) {
						ll u=pop(visited);
						ord[u]=n;
						ids[u]=group_num;
						if(u==v) break;
					}
					group_num++;
				}
			};
			fori(i,0,n) if(ord[i]==-1) dfs(dfs,i);
			forx(x,ids) x=group_num-1-x;
			return {group_num,ids};
		}
	};
}