2017-09-23 2023-04-05 约 4200 字预计阅读 9 分钟 - 次阅读 - 条评论

Tarjan——强连通分量&最近公共祖先（LCA）

写在前面：这是我高二时给高一学弟学妹们唯二的讲课之一。时光荏苒，如今我早已AFO，将讲课内容整理如下，也为了纪念共同奋斗于OI的那些人，那些时光。
写在前面的后面：时间仓促，不甚严谨，难免纰漏，敬请指正。
写在前面的后面的后面：下文中的一些概念可能并没有严谨的依据，只是我为了方便理解构造的，还请谅解。

今天我们来讲讲Tarjan的两个算法：求最近公共祖先和强连通分量。

Tarjan？

Robert Tarjan，美国计算机科学家，1985年开始任教于普林斯顿大学。
发明了TarjanLCA，Tarjan强连通、割点、桥、缩点，斐波纳契堆，Splay，Link-Cut-Trees……
~~将会成为很多OIer心中的天使与恶魔。~~

TarjanLCA

TarjanLCA是离线算法。

离线？

概念

对于“询问－回答”式的问题：

在线算法

进行充分的预处理
每次询问时花少量的时间直接输出答案

离线算法

将所有的询问读入
处理所有的询问
按读入顺序输出答案

打个比方：（友情出演：张小直）

在线算法——

离线算法——

优点

并不需要按顺序处理询问，可以集中统筹解决
常常有更好的效率
一些题目中可以“穿越时空”达到神奇的效果

缺点

难以实现交互
需要额外空间存放询问

现在我们回到Tarjan提出的求LCA的算法。

主要思路

在DFS遍历每个节点时，顺带询问中求有关这个节点的LCA
巧妙利用了并查集和dfs的顺序

过程

注：下面提到的f[i]指并查集中的父亲指针。

伪代码

初始化：f[i]=i

DFS(A)
    标记B已访问
    对于每个A点的询问(A,B)，
    	如果已经访问B
   			LCA=B所在并查集的根
    将k的并查集与其父亲合并（或者说指向父亲）

上面是主要的步骤。

下面我们分开不同过程分析。

并查集

初始时：f[i]=i

每次退出某节点i时
    在并查集中将i与其父亲节点合并
    （f[i]直接指向父亲节点）

DFS

定义“正在访问“：

若DFS进入A点且还未退出A点，则称A点“正在访问”

那么DFS当前正在遍历A点的子树。

~~我不会告诉你这个词是我随便取的~~

性质

当前DFS到A时，仅从A点到root的路径上的点（以及A子树中的部分点）“正在访问”；

**因此A点到root路径上的点i都满足f[i]=i。**这个在后面还会用到。

求LCA

对于每个A点的询问(A,B)，
	如果已经访问过B：
		LCA(A,B)=B所在并查集的根

LCA的充要条件

现在我们已经知道了TarjanLCA的基本过程，那么为什么这样操作就能求出LCA？

从LCA的概念入手。

公共祖先：

是A的祖先
是B的祖先

证明

于是利用上面的信息，再结合过程，可以证明根据TarjanLCA的算法能得到所求的LCA。

公共祖先：

是B的祖先：
- 因为每次更新并查集时，我们都将某个节点的f[i]指向它的父亲节点，所以B所在并查集的根一定是B的祖先。
是A的祖先：
- 因为A“正在访问”
  - 反证法：设B所在并查集的根为L，
    若L不是A的祖先，则L不满足”正在访问“；
    又L为并查集的根，有f[L]=L，尚未指向其父亲节点；
    那么DFS还未进入L；但是这与”B在L的子树中且B已经访问过“矛盾。

代码

这些细节值得关注：

vis[k]=true;的位置
f[v]=k; 的意义
使用邻接链表存储询问
使用cnt优化

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/*
	Tarjan LCA by du33169
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
using namespace std;
template<typename T>
inline void read(T& w)//读入优化 
{
	char r;int f=1;
	for(r=getchar();(r<48||r>57)&&r!='-';r=getchar());
	if(r=='-')r=getchar(),f=-1;
	for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
	w*=f;
}
const int maxn=500003;
const int maxm=500003;
int n,m,root;
struct EDGE 
{
	int to,nxt;
	inline void init(int too,int nxtt)
	{
		to=too,nxt=nxtt;
	}
}edge[maxn<<1];
int ek=0;

int node[maxn];
inline void addEdge(int from,int too)
{
	edge[++ek].init(too,node[from]);
	node[from]=ek;
}

struct QUERY
{
	int id,to,nxt;
	inline void init(int idd,int too,int nxtt)
	{
		id=idd,to=too,nxt=nxtt;
	}
}query[maxm<<1];
int qk=0;

int ask[maxn];//存放每个点的询问链表起始位置 
inline void addQuery(int from,int too,int idd)
{
	query[++qk].init(idd,too,ask[from]);
	ask[from]=qk;
}

int lca[maxn];
void input()
{
	read(n),read(m),read(root);
	int x,y;
	for(int i=1;i<=n-1;++i)
	{
		read(x),read(y);
		addEdge(x,y);
		addEdge(y,x);
	}
	for(int i=1;i<=m;++i)
	{
		read(x),read(y);
		addQuery(x,y,i);
		addQuery(y,x,i);
	}
}

int f[maxn];
bool vis[maxn];
inline int findf(int x)
{
	if(f[x]!=x)
		f[x]=findf(f[x]);
	return f[x];
}
inline void initf()
{
	for(int i=1;i<=n;++i)
		f[i]=i;
}
int cnt=0;
inline void Tarjan(int k)//k相当于前文中的A
{
	vis[k]=true;
	for(int i=node[k];i&&cnt!=m;i=edge[i].nxt)
	{
		int v=edge[i].to;
		if(!vis[v])
		{
			Tarjan(v);
			f[v]=k;
		}
	}
	
	for(int i=ask[k];i&&cnt!=m;i=query[i].nxt)
	{
		int v=query[i].to;//v相当于前文中的B
		if(vis[v]&&!lca[query[i].id])
         /*!!由于处理A的询问在DFS遍历完A的子树之后进行，
         对于B在A子树中的情况会造成重复处理。
         如果使用了cnt优化，必须加以判断，
         否则会导致前面的询问重复计算，”抢占后面的询问的名额”。
         或者可以将处理询问放在DFS前面，确保每个询问只处理一次。*/
		{
			lca[query[i].id]=findf(v);
			++cnt;
		}
	}
}
void output()
{
	for(int i=1;i<=m;++i)
	{
		printf("%d\n",lca[i]);
	}
}
int main()
{
	input();
	initf();
	Tarjan(root);
	output();
	return 0;
}

与倍增LCA的简单比较

	倍增LCA	TarjanLCA
预处理	需要预处理	无需预处理
在线/离线	可以在线	必须离线
时间复杂度	O((n+q)logn)	O(n+q)

习题

同各种LCA题

Tarjan求强连通分量

强连通分量

概念

强连通：在有向图中，从a出发能到达b，且从b出发能到达a，则称a,b强连通 强联通图：任意两个点均强连通的有向图 强连通分量：有向图的

\[极大\]\[强连通\]

子图极大：对于强连通分量中每个点，所有与它强连通的点一定都在这个强连通分量中。（即图中没有点可以再加入到这个强连通分量里）

求法

无向图的连通分量：并查集

有向图：

Kosaraju
Tarjan

当然，接下来我们要讲的是Tarjan算法。

高能预警：Tarjan求强连通分量的算法确实很难理解，我也不能保证讲清楚。如果实在无法理解，为了您的生命安全，请不要苦思冥想，代码会写即可。

主要思路

（先假设有个神奇的魔法可以判断完整的强连通分量）

维护一个栈（基于DFS序）

伪代码：

DFS(k)

将k入栈
枚举k的出边k->v
- DFS (v)
如果从k到栈顶的元素是一个完整的强连通分量：
- 将包括k到栈顶的所有元素弹出，记录
如果不是，或不完整：
- do nothing，k仍然留在栈中

同样的，接下来我们分开来讲。

DFS序

概念

按照DFS的顺序排列节点得到的序列。

示例

如图所示树的DFS序为：8594321

性质

一棵树的子树在DFS序中是连续的一段区间。

※搜索树

概念

DFS时，根据节点的访问关系得到的树

即：

如果在原图中有一条边k->v，
且dfs(k)时通过这条边调用了dfs(v)

那么k->v也存在于搜索树中.

性质

是原图的子图

示例

这是一个图——

假设从0号节点开始搜索，可以得到这样的搜索树：

环

概念

略

特点

是最简单的强连通分量

强连通分量中一定有环（除孤立的一个点外）

性质

若A，B在同一个环中，则A，B属于同一个强连通分量

栈

Point

DFS进入k时，栈中在k之前的点一定能到达k

证明

假设栈中A不能到达k：

有两种情况：

1.在搜索树中A是k的祖先
那么A一定可以到达k
2.A不是k的祖先
- 首先一定不存在A到k直接的边
- 否则k会在访问A后被访问
- 然后A要到达k一定要经过LCA
  - LCA一定能到达k
  - 如果A不能到达k
  - 那么A一定不能到达LCA
  - 那么A与LCA不在同一个强连通分量
  - 那么A在返回LCA之前会被弹出
  - 所以A不会在栈中

如图所示：

证明

同样地，接下来我们来证明这样做是可行的。

~~我不会告诉你们“纯净性”和“完整性”这两个名字也是我自己取的~~

”纯净性“

k到栈顶的区间中不会出现其他强连通分量的点。
如果有其他强连通分量的点
那么这些点一定属于其他的强连通分量
那么这些点会在返回k之前就被弹出

”完整性“

属于k所在强连通分量的点都将在这段区间中
在同一个强连通分量的点在搜索时一定是上下连贯的
或者说对于一个点，
如果它所在的强连通分量中的元素不止一个，
那么在搜索树中下列情况至少出现其一：（显然）
- 他的父亲和它在同一个强连通分量
- 他的儿子中至少有一个和它在同一个强连通分量

判断

先定义一个概念和两个数组：

时间戳

DFS时进入当前节点的访问序号（第几个访问到）

数组

dfn[k]存放k点的时间戳

low[k]存放从k点出发能到达的点的最小时间戳

做法

利用dfn[k]和low[k]之间的关系判断强连通分量

”绑定“

~~我不会告诉你们这个词还是我随便取的~~

思路

在搜索树中不断寻找环，将同一个环的两个点绑定
返回k点时将所有绑定到它的点弹出

实现

设一个“指针”：low[k]
记录k能到达栈中最早的点x，low[k]=dfn[x]
由于栈中k之前的点都能到达k
所以x与k形成了一个环
- 它们在同一个强连通分量中
可以将这样的操作称为：将k绑定至x
- （绑定至较早访问的点）

求low[k]

对于k能一步到达的点v

v能到的点：k也能到

low[v]代表了k经过v能够到达的点的最小时间戳：

直接拿来更新low[k]即可：Low[k]=min{low[vi]}

过程

伪代码

DFS(k)
初始化：
- dfn[k]=low[k]=当前时间戳
将k入栈
枚举k的出边k->v：
- 如果未访问： DFS(v)
  Low[k]=min(low[k],low[v])
- 如果已经访问：
  - 如果在栈中：
    Low[k]=min(low[k],dfn[v])
  - 否则不在栈中：
    已经被弹出，那么不存在环，不用考虑
最后，如果dfn[k]==low[k]
弹出栈中从栈顶到k的所有点，
这些点都处于同一个强连通分量

再判断

low[k]>dfn[k] 不可能，因为low[k]初值为dfn[k]
low[k] <dfn[k] 设low[k]=dfn[x] ,k被绑定至x
所以等到返回x时再弹出
dfn[k]==low[k] K没有被绑定到更早的点：
- k是单独的一个点
或
- k为当前强连通分量最早被访问的点
  可以弹出

辨析

Low[k]=min(low[k],dfn[v]) /low[k]=min(low[k],low[v])？

设low[v]=dfn[x] 此时v已经绑定到x

如果用low[v]：直接将k绑定到x
如果用dfn[v]：先将k绑定到v

最终效果是一样的。

主要代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

int sck=0;
//强连通分量计数 
int belong[maxn];
//belong[i]存放i所在的强连通分量 

int dfn[maxn],low[maxn];
bool in[maxn];
int tid=0;
//时间戳计数器 

//栈stk请自己实现 
void Tarjan(int k)
{
    dfn[k]=low[k]=++tid;
    stk.push(k);
    in[k]=true;
    for(int i=node[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(!dfn[v])//=v is not visited
        {
            Tarjan(v);
            if(low[v]<low[k])
                low[k]=low[v];
        }
        else if(in[v]&&dfn[v]<low[k])
            low[k]=dfn[v];
    }
    if(dfn[k]==low[k])//that is a SCC
    {
        ++sck;
        do
		{	t=stk.top();	
			belong[t]=sck;
			in[t]=false;
			stk.pop();
		}while(t!=k);
    }
}
void solve()
{
	for(int i=1;i<=n;++i)
	{
		if(!dfn[i])
			Tarjan(i);
	}
}

应用

缩点

将一个强连通分量缩成一个点，根据原图的边在新点之间连边，然后就变成了一个有向无环图（DAG），可以在一些情况下简化问题

适用

文件分发、信息传递、捆绑销售等问题。

习题

Luogu2661（NOIP2015）

Luogu2746（数据比Poj强）

Luogu1262

Poj2186 （！单测试点多组数据）

Poj1904

~~看着做吧我已经不会判断难度了~~

Tarjan——强连通分量&最近公共祖先（LCA）

Tarjan——强连通分量&最近公共祖先（LCA）

Tarjan？

TarjanLCA

离线？

概念

在线算法

离线算法

打个比方：（友情出演：张小直）

优点

缺点

主要思路

过程

伪代码

并查集

DFS

定义“正在访问“：

性质

求LCA

LCA的充要条件

公共祖先：

最近：

证明

公共祖先：

最近：

代码

与倍增LCA的简单比较

习题

Tarjan求强连通分量

强连通分量

概念

求法

主要思路

DFS序

概念

示例

性质

※搜索树

概念

性质

示例

环

概念

特点

性质

栈

Point

证明

证明

”纯净性“

”完整性“

判断

时间戳

数组

做法

”绑定“

思路

实现

求low[k]

过程

伪代码

再判断

辨析

主要代码

应用

缩点

适用

习题