Tarjan算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了Tarjan算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Tarjan算法

1 算法简介

还记得无向图判连通块吗？对于无向图中，判连通块是一件很容易的事。你只需要dfs(深度优先搜索)一下就可以了。但是，如果我们把无向图换成有向图呢？

这就是另一个故事了…

2 算法定义

Robert Tarjan计算机科学家，以LCA,Tarjan等算法闻名。Tarjan是求强连通分量的一个强力的算法。

要理解Tarjan这个算法，我们先讲几个定义：

强连通分量 :

对于一个分量，若任意两个点相通，则称为强连通分量。

树边 :

对于一个图的dfs树，它的树边便是此图的树边。

返祖边 :

对于一个图的dfs树，可以使得儿子节点返回到它的祖先的边为返祖边。

横插边 :

对于一个图的dfs树，可以使得一个节点到达另一个节点且它们互不是祖先的边为横插边。

神奇海螺结束！

tarjan算法,图论,# Tarjan,算法,图论,c++

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

这题是一道赤裸裸的强连通分量，晾一下代码。文章来源地址https://www.toymoban.com/news/detail-623939.html

# 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;
}