16 vector<vector<
int>> g2(n);
17 for(
int i=0; i<n; i++)
for(
int j: g[i]) g2[j].push_back(i);
18 vector<
int> order,component(n,-1),seen(n,
false);
20 auto dfs=[&](
auto dfs,
int now)->
void {
22 for(
int nxt: g[now])
if(!seen[nxt]) dfs(dfs,nxt);
26 auto dfs2=[&](
auto dfs2,
int now,
int idx)->
void {
28 for(
int nxt: g2[now])
if(component[nxt]==-1) dfs2(dfs2,nxt,idx);
31 for(
int i=0; i<n; i++)
if(!seen[i]) dfs(dfs,i);
33 reverse(order.begin(),order.end());
35 for(
int now:order)
if(component[now]==-1) dfs2(dfs2,now,idx),idx++;
37 int n_n=*max_element(component.begin(),component.end())+1;
38 vector<vector<
int>> ret(n_n),ret2(n_n);
39 for(
int i=0; i<n; i++) ret[component[i]].push_back(i);
40 for(
int i=0; i<n; i++)
for(
int j: g[i])
if(component[i]!=component[j]) ret2[component[i]].push_back(component[j]);
41 for(
int i=0; i<n_n; i++) UQ(ret2[i]);
43 return {ret,ret2,component};