Beyond the Void

[有向图强连通分量]

在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。

下图中，子图{1,2,3,4}为一个强连通分量，因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量。

直接根据定义，用双向遍历取交集的方法求强连通分量，时间复杂度为O(N^2+M)。更好的方法是Kosaraju算法或Tarjan算法，两者的时间复杂度都是O(N+M)。本文介绍的是Tarjan算法。

[Tarjan算法]

Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出，

Low(u)=Min
{
    DFN(u),
    Low(v),(u,v)为树枝边，u为v的父节点
    DFN(v),(u,v)为指向栈中节点的后向边(非横叉边)
}

当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。

算法伪代码如下

tarjan(u)
{
	DFN[u]=Low[u]=++Index                      // 为节点u设定次序编号和Low初值
	Stack.push(u)                              // 将节点u压入栈中
	for each (u, v) in E                       // 枚举每一条边
		if (v is not visted)               // 如果节点v未被访问过
			tarjan(v)                  // 继续向下找
			Low[u] = min(Low[u], Low[v])
		else if (v in S)                   // 如果节点v还在栈内
			Low[u] = min(Low[u], DFN[v])
	if (DFN[u] == Low[u])                      // 如果节点u是强连通分量的根
		repeat
			v = S.pop                  // 将v退栈，为该强连通分量中一个顶点
			print v
		until (u== v)
}

接下来是对算法流程的演示。

从节点1开始DFS，把遍历到的节点加入栈中。搜索到节点u=6时，DFN[6]=LOW[6]，找到了一个强连通分量。退栈到u=v为止，{6}为一个强连通分量。

返回节点5，发现DFN[5]=LOW[5]，退栈后{5}为一个强连通分量。

返回节点3，继续搜索到节点4，把4加入堆栈。发现节点4向节点1有后向边，节点1还在栈中，所以LOW[4]=1。节点6已经出栈，(4,6)是横叉边，返回3，(3,4)为树枝边，所以LOW[3]=LOW[4]=1。

继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以LOW[2]=DFN[4]=5。返回1后，发现DFN[1]=LOW[1]，把栈中节点全部取出，组成一个连通分量{1,3,4,2}。

至此，算法结束。经过该算法，求出了图中全部的三个强连通分量{1,3,4,2},{5},{6}。

可以发现，运行Tarjan算法的过程中，每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次，所以该算法的时间复杂度为O(N+M)。

求有向图的强连通分量还有一个强有力的算法，为Kosaraju算法。Kosaraju是基于对有向图及其逆图两次DFS的方法，其时间复杂度也是O(N+M)。与Trajan算法相比，Kosaraju算法可能会稍微更直观一些。但是Tarjan只用对原图进行一次DFS，不用建立逆图，更简洁。在实际的测试中，Tarjan算法的运行效率也比Kosaraju算法高30%左右。此外，该Tarjan算法与求无向图的双连通分量(割点、桥)的Tarjan算法也有着很深的联系。学习该Tarjan算法，也有助于深入理解求双连通分量的Tarjan算法，两者可以类比、组合理解。

求有向图的强连通分量的Tarjan算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的Tarjan算法，以及求最近公共祖先的离线Tarjan算法，在此对Tarjan表示崇高的敬意。

附：tarjan算法的C++程序

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

void tarjan(int i)
{
	int j;
	DFN[i]=LOW[i]=++Dindex;
	instack[i]=true;
	Stap[++Stop]=i;
	for (edge *e=V[i];e;e=e->next)
	{
		j=e->t;
		if (!DFN[j])
		{
			tarjan(j);
			if (LOW[j]<LOW[i])
				LOW[i]=LOW[j];
		}
		else if (instack[j] && DFN[j]<LOW[i])
			LOW[i]=DFN[j];
	}
	if (DFN[i]==LOW[i])
	{
		Bcnt++;
		do
		{
			j=Stap[Stop--];
			instack[j]=false;
			Belong[j]=Bcnt;
		}
		while (j!=i);
	}
}
void solve()
{
	int i;
	Stop=Bcnt=Dindex=0;
	memset(DFN,0,sizeof(DFN));
	for (i=1;i<=N;i++)
		if (!DFN[i])
			tarjan(i);
}

[参考资料]

• Wikipedia
• Amber的图论总结

BYVoid 原创作品，转载请注明。

我的计划就从NOI1997开始。NOI1997一共有6道题，分别是[卫星覆盖][积木游戏][竞赛排名][最佳游览][最优乘车][文件匹配]。这一年的6个题难易分布均衡，做完后收获不小。

其中[竞赛排名]和[最佳游览]是两个最简单的题，但是往往细节是容易忽视的。[积木游戏]和[最优乘车]难度属于中等，分别是动态规划和构造最短路径解题。[卫星覆盖]和[文件匹配]属于较难题，用到了[卫星覆盖]离散化或者立体切割的方法，而[文件匹配]是搜索中的难题，需要很多的优化。

做这些题我花了4天的时间，进度还算正常，希望能继续保持下去。今后做题的宗旨是“不求多，不求快，但求精”。

Read the rest of this entry »

题上描述这种图是很特殊的，每个顶点只有一条指出去的有向边，而且一定存在一个环，哪怕是自环，从任意一个顶点出发，最终一定进入一个环。我们的任务的判断这样的两个图是否同构。

首先，这个图不一定是弱连通的，可能会有多个连通分量，我们需要考虑每个连通分量。每个连通分量中一定存在一个环，去掉环上的边以后，剩下 的是一个森林，每棵树都是内向树。实际上它是环状内向树森林。对于两个内向树，我们可以很容易地判断它们是否同构，于是我们有了解决问题的方法。

首先是两个内向树，如果它们同构，它们的括号序列一定相同，反之也成立。判断两个环状内向树森林同构，首先应该满足环的大小相同，如果两 个环的顶点数都不一样，那么它们一定不会同构。如果环大小相同，则需要枚举两个环上的对应点，然后判断以环上每个顶点为根的内向树是否都同构。用上述方法 可以判断两个连通分量是否同构，对于题中给的两个图，首先判断连通分量的个数是否相同，然后用搜索的方法确定一个对应关系，以此判断每个每对连通分量是否 同构。如果存在一种对应方案使得所有的连通分量通过，那么这两个图同构。

上述方法中，生成所有内向树括号序列需要O(N^2logN)时间(需要排序)，枚举每个环的对应关系需要O(N)，判断两个内向树括号 序列相同需要O(N)，枚举连通分量间的对应关系由于是搜索，尽管实际搜索的很少，但是从时间复杂度上分析仍然是O(N!)。每个文件有D个测试数据，于 是总的时间复杂度是O((N^2logN+N^2*N!)*D)。但是实际上这个时间复杂度由于全部从最坏情况考虑(实际上所有最坏的情况不可能同时达 到)，所以是相当悲观的估计。实际编程对于N<=2000，已经可以完全应付了。

在编程实现的时候，许多地方要用到链表，否则空间是不够用的。细节不容忽视。

关于内向树以及生成括号序列，请参看有向树与树的括号序列表示法。
Read the rest of this entry »

[有向树] 一个弱连通有向图，若去掉方向后得到一棵树，则称此有向图为一棵有向树，记为T。

[外向树] 若一个有向树T，有且只有一个顶点入度为0，其余顶点入度都为1，则称T为外向树。T中入度为0的节点被称为T的根节点，出度为0的节点被称为T的叶节点。每个节点的有向边指向的节点被称为该节点的子节点。

[内向树] 若一个有向树T，有且只有一个顶点出度为0，其余顶点出度都为1，则称T为内向树。T中出度为0的节点被称为T的根节点，入度为0的节点被称为T的叶节点。每个节点的有向边的反向边指向的节点被称为该节点的子节点。

外向树和内向树都是有根树。

图1	图2

如上，图1为一棵外向树，图2为一棵内向树。

[树的括号序列最小表示法]

定义S[t]表示以t为根的子树的括号序列

S[t]=

{

‘(‘,’)’ (如果t为叶节点)

‘(‘,S[c1],S[c2],…,S[ck],’)’ (c1,c2,…,ck为t的k个子节点，S[c1],S[c2],…,S[ck]要按照字典序排列)

}

为了保证同构的树的括号序列表示具有唯一性，我们必须规定子树点的顺序。按照子树的括号序列的字典序就是一种不错的方法。

例如上述图2，它的括号序列最小表示就是((()()())())。

[有根树的同构]

对于一个有根树，我们可以通过比较他们的括号序列的最小表示，如果他们的括号序列最小表示完全相等，那么他们同构。

BYVoid 原创讲解，转载请注明。

这道题的解决方法隐藏得很深，不经过严密的数学推理分析是很难想到正确方法的。

注意到题上的一个看似无关紧要的条件，“不包括三角形”，这是一个突破口。由这个条件，我们可以证明，如果一个图不存在度数为1的顶点，B永远也追不上A。也就是B想追上A，必须让A“走投无路”。

于是我们首先把原图处理一下，求出对于A来说的安全区。对于A来说的安全区，也就是一个没有度为1的顶点的最大子图。我们把这个安全区求出，并标记上。

A要想不被B抓住，则一定要向安全区中逃跑。如果A能够在B追上A之前逃离到安全区，则B就永远也追不上A。否则，A无论如何也会被B追上。在A“必死无疑”的时候，A要想尽可能晚的被B追上，就必须想远离B的方向跑。

有了以上的分析，得出下列算法
1、求出安全区的顶点。
2、分别求出A，B初始位置开始，到每个顶点的距离，记作DA[i]和DB[i]。
3、若存在安全区中的顶点k，使得DA[k] 4、如果不存在上述顶点k，则找到满足DA[i]

时间复杂度：O(M+N)
Read the rest of this entry »