[Tarjan] Tarjan详细介绍(顺手写版本)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
int n,m;
int head[maxn];
int tim,cnt;
struct node {
  int v;
  int nex;
} e[maxn];
void init() {
  cnt = 0;
  tim = 0;
  for(int i=1; i<=n; i++) {
    head[i] = -1;
  }
}
void add(int u,int v) {
  e[cnt].v = v;
  e[cnt].nex = head[u];
  head[u] = cnt ++;
}
stack<int> st; 
//low[x] -> x or x子树能够到达的栈中节点的次序号 
int dfn[maxn],low[maxn],pos[maxn];
int tot;
/// pos[i] == x -> 点i在第x个强连通分支 
void Tarjan(int x) {
  dfn[x] = low[x] = ++tim;///时间戳 
  st.push(x);///节点入栈 
  for(int i=head[x]; ~i; i=e[i].nex) {
    int v = e[i].v;///有向边 
    if(!dfn[v]) {//节点v没有被访问过，是树枝边 
      Tarjan(v);//首次被访问不在栈内 
      low[x] = min(low[x],low[v]);
    } else if(!pos[v]) {///被访问过，在栈内 
    //遇到已经在栈内的点，就将该点作为强连通分量的根 
      low[x] = min(low[x],dfn[v]);
    }
  }//low[x] 没有更新，在栈中节点u以及之上节点构成一个强连通分支 
  if(low[x] == dfn[x]) {
    pos[x] = ++tot;///记录强连通分支的个数 
    while(st.top() != x) {
      pos[st.top()] = tot;//栈中节点u以及之上节点在第tot个强连通分支中 
      st.pop();
    }
    st.pop();//节点u出栈 
  }
}
int main() {
  cin >> n >> m;
  init();
  for(int i=1; i<=m; i++) {
    int a,b;
    cin >> a >> b;
    add(a,b);
  }
  Tarjan(1);///wrong
  for(int i=1;i<=n;i++){///yes
    if(dfn[i] == 0) Tarjan(i);
  }
  cout<<tot<<endl;
  return 0;
}