tarjan
<pre><code class="language-cpp">#include<iostream>
#include<stack>
#include<vector>
using namespace std;
const int maxn = 1e6+5;
int n, m;
vector<int> edge[maxn];
namespace SCC{
int cnt, cntb;
vector<int> belong[maxn];
bool instack[maxn];
int dfn[maxn];
int low[maxn];
stack<int> s;
void init(){
cnt = cntb = 0;
stack<int> _s;
swap(_s, s);
for(int i = 1; i < n; i++){
edge[i].clear();
belong[i].clear();
instack[i] = false;
dfn[i] = low[i] = 0;
}
}
void Tarjan(int u){
dfn[u] = low[u]= ++cnt;
s.push(u);
instack[u] = true;
for(int i = 0; i < edge[u].size(); i++){
int v = edge[u][i];
if(!dfn[v]){
Tarjan(v);
low[u] = min(low[u], low[v]);
}else if(instack[v]) low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u]){
++cntb;
while(233){
int node=s.top();
s.pop();
instack[node] = false;
belong[cntb].push_back(node);
if(node == u) break;
}
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
edge[u].push_back(v);
}
SCC::Tarjan(1);
cout << "id :";
for(int i = 1; i <= n; i++)
cout << i << " ";
cout << endl;
cout << "dfn :";
for(int i = 1; i <= n; i++)
cout << SCC::dfn[i] << " ";
cout << endl;
cout << "low :";
for(int i = 1; i <= n; i++)
cout << SCC::low[i] << " ";
cout << endl;
for(int i = 1; i <= SCC::cntb; i++){
cout << "SCG " << i << " : ";
for(int j = 0; j < SCC::belong[i].size(); ++j)
cout << SCC::belong[i][j] << " ";
cout << endl;
}
return 0;
} </code></pre>