# [图论] 求强联通分量

## 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <vector>

using namespace std;
const int MAXN = 100000 + 10;
const int MAXM = 200000 + 10;

int Head[MAXN], to[MAXM], Next[MAXM], tot = 1;
int dfn[MAXN], low[MAXN], time_stamp;

stack <int> Sta;
vector <int> scc[MAXN];
int sccNo[MAXN], scc_cnt;

int n, m;

int x = 0;
char ch = getchar();

while(ch < '0' || ch > '9'){
ch = getchar();
}

while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}

return x;
}

inline void add(int a, int b){
to[tot] = b;
}

inline void tarjan(int x){
dfn[x] = low[x] = ++time_stamp;

Sta.push(x);

int v = to[i];

if(!dfn[v]){
tarjan(v);
low[x] = min(low[x], low[v]);
}else if(!sccNo[v]){
low[x] = min(low[x], dfn[v]);
}
}

if(dfn[x] == low[x]){
scc_cnt++;

while(true){
int tmp = Sta.top();
Sta.pop();

sccNo[tmp] = scc_cnt;
scc[scc_cnt].push_back(tmp);

if(tmp == x){
break;
}
}
}
}

inline void find_scc(){
for(register int i=1; i<=n; i++){
if(!dfn[i])
tarjan(i);
}
}