Tarjan算法求强联通分量基于对图的DFS：
-
表示
节点在DFS搜索中是第几个被搜索到的（时间戳）。
-
表示从在DFS搜索树中以
的最小值。
在进行DFS时，需要维护一个栈。在开始对节点进行DFS时，初始化
dfn[u] = low[u] = ++timer;，然后将节点压入栈。之后遍历每一条以节点
为起点的边
，这时会有三种情况：
- 节点
已被DFS搜索过了，并且节点
- 节点
low[u] = min(low[u], dfn[v]);。 - 节点
low[u] = min(low[u], low[v]);。
需要使用到的全局变量的定义：
int N; // N表示节点总个数
vector <int> E;
int dfn[MAXN], low[MAXN], timer;
int scc[MAXN], cnt; // scc[x]表示节点x所在强联通分量的编号
stack <int> St;
DFS搜索可以如下实现（参考代码）：
void dfs(int u){
dfn[u] = low[u] = ++timer;
St.push(u);
for(int i=0;i<E[u].size();i++){
int v = E[u][i];
if(scc[v]) continue;
if(dfn[v]) low[u] = min(low[u], dfn[v]);
else{
dfs(v);
low[u] = min(low[u], low[v]);
}
}
if(dfn[u]==low[u]){
scc[u] = ++cnt;
while(St.top()!=u){
scc[St.top()] = cnt;
St.pop();
}
St.pop();
}
}
Tarjan算法只需要调用上面的dfs函数即可，代码如下：
void Tarjan(){
for(int i=1;i<=N;i++){
if(!dfn[i]) dfs(i);
}
}
附上一道练习题，链接：Codevs 2822爱在心中。
思路：该题需要先使用Tarjan算法求强联通分量，然后统计所有节点数大于1的强联通分量的个数。判断是否存在被其他所有人或爱心天使所爱的爱心天使的方法是：统计每一个强联通分量的出度，被其他所有人或爱心天使所爱的爱心天使代表的强联通分量的出度必定为0。统计出度为0的强联通分量的个数，假如不为1则不存在，否则可能存在。在可能存在的情况下，从唯一的出度为0的强联通分量出发，在反向图中看能否遍历所有节点，如果可以则该强联通分量即为所求爱心天使，否则依然不存在。
AC代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int MAXN = 100000+10;
int N, M;
vector <int> E[MAXN], E2[MAXN], SCC[MAXN];
int dfn[MAXN], low[MAXN], timer;
int scc[MAXN], outd[MAXN], cnt;
stack <int> St;
bool vis[MAXN];
void dfs(int u){
dfn[u] = low[u] = ++timer;
St.push(u);
for(int i=0;i<E[u].size();i++){
int v = E[u][i];
if(scc[v]) continue;
if(dfn[v]) low[u] = min(low[u], dfn[v]);
else{
dfs(v);
low[u] = min(low[u], low[v]);
}
}
if(dfn[u]==low[u]){
scc[u] = ++cnt;
SCC[cnt].push_back(u);
while(St.top()!=u){
scc[St.top()] = cnt;
SCC[cnt].push_back(St.top());
St.pop();
}
St.pop();
}
}
void Tarjan(){
for(int i=1;i<=N;i++){
if(!dfn[i]) dfs(i);
}
}
void dfs2(int u){
vis[u] = 1;
for(int i=0;i<E2[u].size();i++)
if(!vis[E2[u][i]]) dfs2(E2[u][i]);
}
int main(){
scanf("%d%d", &N, &M);
while(M--){
int from, to;
scanf("%d%d", &from, &to);
E[from].push_back(to);
E2[to].push_back(from);
}
Tarjan();
int ans = 0, t = 0;
for(int i=1;i<=cnt;i++) if(SCC[i].size()>1) ans++;
printf("%d\n", ans);
for(int i=1;i<=N;i++)
for(int j=0;j<E[i].size();j++)
if(scc[i]!=scc[E[i][j]]) outd[scc[i]]++;
for(int i=1;i<=cnt;i++)
if(!outd[i]){
t++;
ans = i;
}
bool f = 0;
if(t==1 && SCC[ans].size()>1){
f = 1;
dfs2(SCC[ans][0]);
for(int i=1;i<=N;i++) if(!vis[i]) f = 0;
}
if(f){
sort(SCC[ans].begin(), SCC[ans].end());
for(int i=0;i<SCC[ans].size();i++)
printf(i<SCC[ans].size()-1?"%d ":"%d\n", SCC[ans][i]);
}
else printf("-1\n");
return 0;
}
