Tarjan算法
1 算法简介
还记得无向图判连通块吗？对于无向图中，判连通块是一件很容易的事。你只需要dfs(深度优先搜索)一下就可以了。但是，如果我们把无向图换成有向图呢？
这就是另一个故事了……
2 算法定义
Robert Tarjan计算机科学家，以LCA,Tarjan等算法闻名。Tarjan是求强连通分量的一个强力的算法。
要理解Tarjan这个算法，我们先讲几个定义：
强连通分量 :
对于一个分量，若任意两个点相通，则称为强连通分量。
树边 :
对于一个图的dfs树，它的树边便是此图的树边。
返祖边 :
对于一个图的dfs树，可以使得儿子节点返回到它的祖先的边为返祖边。
横插边 :
对于一个图的dfs树，可以使得一个节点到达另一个节点且它们互不是祖先的边为横插边。
神奇海螺结束！
3 算法详细
先讲一下我们要用到的数组。
-
dfn:第\(i\)个节点他的时间戳 -
low:第\(i\)个节点他最多经过一条返祖边所能到达的最小时间戳 -
st:一个栈,用来储存当前还未确定但已经扩展过的点 -
co:第\(i\)个节点他所在的强连通分量编号
我们讲一下算法流程。
-
此时来到了点\(u\)
-
扩展他的子节点，这里假设现在到的子节点为\(v\),扩展完了就来到第\(5\)步
-
三种情况：
!dfn[v],即还未扩展的点，则我们直接来到第\(4\)步!co[v]&& dfn[v],即还未出栈但已扩展过的点(就是返祖/横叉了嘛)，我们更新一下\(low_u = \min(low_u, dfn_v)\),并返回第\(2\)步。(看不懂的感性理解一下)co[v] && dfn[v],即已出栈且遍历过，那么我们直接返回第\(2\)步
-
我们先对\(v\)这个顶点扩展一下(即返回第\(1\)步),然后把\(low_u = \min(low_u, low_v)\)更新一下，接着回到第\(2\)步
-
如果\(dfn_u = low_u\),这说明\(u\)没有返祖边,它拥有属于自己的一棵子树，而此时栈中的点又一定能到\(u\)(要不然就被弹掉了)，所以此时我们只需要弹栈就可以了！
-
我们已经完成了所有操作，可以回溯到第\(1\)步了
4 模板代码
先放一道模板题 : CF427C Checkposts
这题是一道赤裸裸的强连通分量，晾一下代码。
# include <bits/stdc++.h>
using namespace std;
# define ll long long
# define lf double
# define GO(i,a,b) for(int i = a; i <= b; i ++)
# define RO(i,b,a) for(int i = b; i >= a; i --)
# define FO(i,u,head,e) for(int i = head[u]; i; i = e[i].next)
# define CI const int
# define pii pair<int,int>
# define MP(a,b) make_pair(a,b)
# define PB(x) push_back(x)
# define mem(a,x) memset(a, x, sizeof a)
# define F first
# define S second
CI maxn = 1e5 + 7;
CI maxm = 3e5 + 7;
CI mod = 1e9 + 7;
int n, m;
struct Edge{
int u, v, next;
}e[maxm];
int head[maxn], cnt;
void add(int u, int v){
e[++ cnt].u = u;
e[cnt].v = v;
e[cnt].next = head[u];
head[u] = cnt;
}
int dfn[maxn];
int low[maxn];
int vis[maxn]; // 0未访问, 1在栈中, 2已访问
int tar[maxn]; // 连通分量
int col;
int tmp;
stack <int> q;
void Tarjan(int u){
q.push(u);
vis[u] = 1; // 在栈中
low[u] = dfn[u] = ++ tmp;
FO (i, u, head, e){
int v = e[i].v;
if (vis[v] == 2)
continue;
if (dfn[v])
low[u] = min <int> (low[u], dfn[v]);
else{
Tarjan(v);
low[u] = min <int> (low[u], low[v]);
}
}
if (dfn[u] == low[u]){
int v = q.top();
q.pop();
col ++;
while (!q.empty() && v != u){
vis[v] = 2;
tar[v] = col;
v = q.top();
q.pop();
}
vis[u] = 2;
tar[u] = col;
}
}
vector <int> poi[maxn];
ll a[maxn];
int main(){
cin >> n;
GO (i, 1, n)
scanf("%lld", &a[i]);
cin >> m;
GO (i, 1, m){
int u, v;
scanf("%d %d", &u, &v);
add(u, v);
}
GO (i, 1, n)
if (!vis[i])
Tarjan(i);
GO (i, 1, n)
poi[tar[i]].PB(i);
ll ans1 = 1, ans2 = 0;
GO (i, 1, col){
ll minn = 2e18;
ll res = 0;
for (int j : poi[i])
minn = min <ll> (minn, a[j]);
for (int j : poi[i])
if (a[j] == minn)
res ++;
ans2 += minn;
ans1 = (ans1 * res) % mod;
}
printf("%lld %lld", ans2, ans1);
return 0;
}
原文地址：http://www.cnblogs.com/yh2021shx/p/16809958.html
