Path-based SCC (Gabow)

path_scc.cpp

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
using ll=long long;

struct path_scc
{
	stack<int,vector<int>>S,P;
	int C=0,Z=0,N;
	vector<int>pn,scc;
	vector<vector<int>>adj;
	path_scc(int n):adj(n),pn(n),scc(n),N(n){}
	void add(int a,int b){adj[a].push_back(b);}
	void dfs(int v)
	{
		if(pn[v])return;
		pn[v]=++C;S.push(v);P.push(v);
		for(int&w:adj[v])
		{
			if(!pn[w])dfs(w);
			else if(!scc[w])while(pn[P.top()]>pn[w])P.pop();
		}
		if(v==P.top())
		{
			Z++;bool f=0;P.pop();
			while(!f){if(S.top()==v)f=1;scc[S.top()]=Z;S.pop();}
		}
	}
	auto process()
	{
		for(int i=0;i<N;i++)dfs(i);
		vector<vector<int>>res(Z);
		for(int i=0;i<N;i++)res[scc[i]-1].push_back(i);
		for(auto&r:res)sort(begin(r),end(r));
		sort(begin(res),end(res));
		return res;
	}
};