一、Tarjan算法求LCA
二、Tarjan算法求强连通分量【栈里存点---------每个点都属于一个强连通分量】
（着重理解一下第11行的else if语句：dfn[ i ]!=0 且 instk[i]==0的点一定已经是另一个强连通分量里面的点了，所以就不用考虑了，所以用else if(instk[ i ])来判断是不是已经是别的强连通分量里的点了，如果不是，则是当前点的祖先，可以用来更新low[ u ]，这也是强连通分量的更新low[ u ]的精髓。）
1 void Tarjan(int u) { 2 dfn[u] = low[u] = ++tim; 3 in_stk[u] = 1; 4 stk[tp++] = u; 5 for (int i = head[u]; i != -1; i = e[i].next) { 6 int v = e[i].to; 7 if (!dfn[v]) { 8 Tarjan(v); 9 if (low[v] < low[u])low[u] = low[v];10 }11 else if (in_stk[v]) {12 if (low[v] < low[u])low[u] = low[v];//这里使用dfn[v]和low[v]都可以13 }14 }15 if (dfn[u] == low[u]) {16 scc_cnt++;17 do {18 tp--;19 int tt = stk[tp];20 col[tt] = scc_cnt;21 in_stk[tt] = 0;22 vc[scc_cnt].push_back(tt);23 } while (stk[tp] != u);24 }25 }
三、Tarjan算法求双连通分量【栈里存边------每条边都属于一个点双连通分量】
（由于是无向图，这里需要注意的是不能重复访问边，用else if(dfn[ u ]>dfn[ v ]&&v!=fa)来防止重复访问）
1 void Tarjan(int u, int fa) { 2 dfn[u] = low[u] = ++tim; 3 int child = 0; 4 for (int i = head[u]; i != -1; i = e[i].next) { 5 int v = e[i].to; 6 struct edge e1; 7 e1.fr = u; e1.to = v; 8 if (!dfn[v]) { 9 stk.push(e1);10 child++;11 Tarjan(v);12 if (low[v] >= dfn[u]) {13 iscut[u] = true;14 bcc_cnt++; bcc[bcc_cnt].clear();15 do {16 struct edge e2 = stk.top(); stk.pop();17 if (col[e2.fr]!=bcc_cnt) {18 bcc[bcc_cnt].push_back(e2.fr);19 col[e2.fr] = bcc_cnt;20 }21 if (col[e2.to]!=bcc_cnt) {22 bcc[bcc_cnt].push_back(e2.to);23 col[e2.to] = bcc_cnt;24 }25 } while (e2.fr != u || e2.to != v);26 }27 }28 else if (dfn[v] < dfn[u] && v != fa) {29 stk.push(e1);30 low[u] = min(low[u], dfn[v]);//注意这里必须是dfn[v]，而不能是low[v],因为low[v]很可能在另一个双连通分量已经被更新，这个时候用会出错31 }32 if (fa < 0 && chile == 1)iscut[u] = false;33 }34 }