Browsed by
分类:GraphTheory

[转载]有向图强连通分量的Tarjan算法

[转载]有向图强连通分量的Tarjan算法

转自:https://www.byvoid.com/blog/scc-tarjan

[有向图强连通分量]

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

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

image

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

[Tarjan算法]

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

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

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

算法伪代码如下

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

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

image

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

image

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

image

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

image

至此,算法结束。经过该算法,求出了图中全部的三个强连通分量{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++程序

 

[参考资料]

 

HDU 1142 A Walk Through The Forest

HDU 1142 A Walk Through The Forest

Problem Description

A Walk Through the Forest

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5891    Accepted Submission(s): 2168

Problem Description
Jimmy experiences a lot of stress at work these days, especially since his accident made working difficult. To relax after a hard day, he likes to walk home. To make things even nicer, his office is on one side of a forest, and his house is on the other. A nice walk through the forest, seeing the birds and chipmunks is quite enjoyable.
The forest is beautiful, and Jimmy wants to take a different route everyday. He also wants to get home before dark, so he always takes a path to make progress towards his house. He considers taking a path from A to B to be progress if there exists a route from B to his home that is shorter than any possible route from A. Calculate how many different routes through the forest Jimmy might take.

 

Input
Input contains several test cases followed by a line containing 0. Jimmy has numbered each intersection or joining of paths starting with 1. His office is numbered 1, and his house is numbered 2. The first line of each test case gives the number of intersections N, 1 < N ≤ 1000, and the number of paths M. The following M lines each contain a pair of intersections a b and an integer distance 1 ≤ d ≤ 1000000 indicating a path of length d between intersection a and a different intersection b. Jimmy may walk a path any direction he chooses. There is at most one path between any pair of intersections.

 

Output
For each test case, output a single integer indicating the number of different routes through the forest. You may assume that this number does not exceed 2147483647

 

Sample Input

Sample Output
2 4

话说这个题和并查集有神马关系啊喂!!想了5个小时没有想到如何用并查集来处理,于是去看别人的博客了这分明是一个最短路+搜索喂     (╯#-_-)╯~~~~~~~~~~~~~~~~~╧═╧ 大力掀

 

好了买萌结束 = =开始学习Dijkstra 算法 以及 可能的话 学习SPFA 算法

Dijkstra算法学习

POJ 1300 Door Man 欧拉路&字符串处理TAT

POJ 1300 Door Man 欧拉路&字符串处理TAT

Door Man
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 2140 Accepted: 859

Description

You are a butler in a large mansion. This mansion has so many rooms that they are merely referred to by number (room 0, 1, 2, 3, etc…). Your master is a particularly absent-minded lout and continually leaves doors open throughout a particular floor of the house. Over the years, you have mastered the art of traveling in a single path through the sloppy rooms and closing the doors behind you. Your biggest problem is determining whether it is possible to find a path through the sloppy rooms where you:

  1. Always shut open doors behind you immediately after passing through
  2. Never open a closed door
  3. End up in your chambers (room 0) with all doors closed

In this problem, you are given a list of rooms and open doors between them (along with a starting room). It is not needed to determine a route, only if one is possible.

Input

Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.
A single data set has 3 components: 

  1. Start line – A single line, “START M N”, where M indicates the butler’s starting room, and N indicates the number of rooms in the house (1 <= N <= 20).
  2. Room list – A series of N lines. Each line lists, for a single room, every open door that leads to a room of higher number. For example, if room 3 had open doors to rooms 1, 5, and 7, the line for room 3 would read “5 7”. The first line in the list represents room 0. The second line represents room 1, and so on until the last line, which represents room (N – 1). It is possible for lines to be empty (in particular, the last line will always be empty since it is the highest numbered room). On each line, the adjacent rooms are always listed in ascending order. It is possible for rooms to be connected by multiple doors!
  3. End line – A single line, “END”

Following the final data set will be a single line, “ENDOFINPUT”.

Note that there will be no more than 100 doors in any single data set.

Output

For each data set, there will be exactly one line of output. If it is possible for the butler (by following the rules in the introduction) to walk into his chambers and close the final open door behind him, print a line “YES X”, where X is the number of doors he closed. Otherwise, print “NO”.

Sample Input

Sample Output

首先,需要搞清楚如何处理输入  参考我的上一篇文章,可知道应该用什么函数进行输入和输出 。 先把输入处理的代码放上 ,下面代码可以把数据读入并且记录每一个节点的度数值

实际上上面代码有问题 ,不过 在我写的时候还没有发现问题所在,下面先说这道题的思路,其实这个题很简单就是一个一笔画问题, 每一个房间代表一个节点,每一个开着的门代表一条节点之间的边,图为无向图,问是否存在从节点 m到 0 的一条路径,使得图中每一个边都被经过仅一次。

没有什么太多需要注意的,直接拿判断条件去判断就可以了,判断条件就是,当 m!=0时  即非Euler回路 ,这时要求 有两个奇节点 m 0 其它节点均为偶节点 当m=0时 要求所有节点均为偶节点 然后 根据边数=度数/2我们可以算出来有多少个门

因此我们只需要开个数组记录一下度数 就好了,

下面是AC代码 之前错了一次 是因为字符处理上出问题了,由于最初我gets读入空行的时候,会当作读入了一个数字 0 结果导致出问题 修改代码后就没有问题了 AC代码如下

 

HDU 1116 Play on words 欧拉路+并查集

HDU 1116 Play on words 欧拉路+并查集

Problem Description

Play on Words

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5576    Accepted Submission(s): 1831

Problem Description

Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.

There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word acm” can be followed by the word motorola”. Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door.

 

Input
The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing a single integer number Nthat indicates the number of plates (1 <= N <= 100000). Then exactly Nlines follow, each containing a single word. Each word contains at least two and at most 1000 lowercase characters, that means only letters ‘a’ through ‘z’ will appear in the word. The same word may appear several times in the list.

 

Output
Your program has to determine whether it is possible to arrange all the plates in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times.
If there exists such an ordering of plates, your program should print the sentence “Ordering is possible.”. Otherwise, output the sentence “The door cannot be opened.”.

 

Sample Input
3 2 acm ibm 3 acm malform mouse 2 ok ok

 

Sample Output
The door cannot be opened. Ordering is possible. The door cannot be opened.
具体实现 用 Euler路+并查集来做
先学习欧拉路去 _(:3 [_)_
好啦在看了各个blog的代码之后总算写对啦   一次AC还好
这个题可以抽象出一个图模型  给出这个例子 (图中的数字代表字母 如 1代表 a  2代表 b … 而 (1,2)就代表一个以a开头以b结尾的单词 ,中间部分无用我们忽略即可 )
以26个字母为节点   以单词的首尾字母为边表示链接关系(这里省略了入度和出度都为0的节点)
如何判断可以开门呢,判断的依据就是用上面的方法产生的图是否为Euler图
这样就需要知道什么是Euler图
Euler图有两种
Euler 通路 和Euler回路  这个题是判断有向图是否存在Euler通路或者Euler回路
下面给出Euler通路和回路的判断定理:

②.欧拉路径存在性的判定一。无向图
一个无向图存在欧拉通路,当且仅当   该图所有顶点的度数为偶数   或者  除了两个度数为奇数外其余的全是偶数。

二。有向图
一个有向图存在欧拉通路 当且仅当有且仅有一个节点的出度-入度=1 有且仅有一个节点的入度-出度=1,其余节点入度=出度

有向图存在欧拉回路 当且仅当各个节点的入度=出度

 

因此 我们就可以根据这个来判断是否为欧拉图  分为两步

1.检查图的连通性

2.检查每个节点的出入度数

检查图的连通性我们要用到的算法就是并查集 每次并查集记录这个节点的父节点,父节点就是它的直接or间接后继节点,最终找到BOSS节点 即所有节点的最终根节点 上图中按照下面的算法BOSS节点就是 6

并查集算法如下:

 

下面给出Union Find算法执行后的运行的图示

红色的表示最后一次执行后,再次对所有的节点进行UF算法 各个节点的BOSS是谁  可以看出来都是 6

如果不连通肯定不能开门,连通的话就要判断一下度数关系,这时候判断一下Euler通路和回路就好

 

因此 我们主要要存的信息是  每个节点的father  每个节点的度数 每个节点是否被访问过的状态,其余的都是一些标记变量 。下面是AC代码 代码较长,应该有很多地方能够简化

 

POJ 1860 Currency Exchange

POJ 1860 Currency Exchange

Currency Exchange

Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 20346 Accepted: 7298

Description

Several currency exchange points are working in our city. Let us suppose that each point specializes in two particular currencies and performs exchange operations only with these currencies. There can be several points specializing in the same pair of currencies. Each point has its own exchange rates, exchange rate of A to B is the quantity of B you get for 1A. Also each exchange point has some commission, the sum you have to pay for your exchange operation. Commission is always collected in source currency.
For example, if you want to exchange 100 US Dollars into Russian Rubles at the exchange point, where the exchange rate is 29.75, and the commission is 0.39 you will get (100 – 0.39) * 29.75 = 2963.3975RUR.
You surely know that there are N different currencies you can deal with in our city. Let us assign unique integer number from 1 to N to each currency. Then each exchange point can be described with 6 numbers: integer A and B – numbers of currencies it exchanges, and real RAB, CAB, RBA and CBA – exchange rates and commissions when exchanging A to B and B to A respectively.
Nick has some money in currency S and wonders if he can somehow, after some exchange operations, increase his capital. Of course, he wants to have his money in currency S in the end. Help him to answer this difficult question. Nick must always have non-negative sum of money while making his operations.

Input

The first line of the input contains four numbers: N – the number of currencies, M – the number of exchange points, S – the number of currency Nick has and V – the quantity of currency units he has. The following M lines contain 6 numbers each – the description of the corresponding exchange point – in specified above order. Numbers are separated by one or more spaces. 1<=S<=N<=100, 1<=M<=100, V is real number, 0<=V<=103.
For each point exchange rates and commissions are real, given with at most two digits after the decimal point, 10-2<=rate<=102, 0<=commission<=102.
Let us call some sequence of the exchange operations simple if no exchange point is used more than once in this sequence. You may assume that ratio of the numeric values of the sums at the end and at the beginning of any simple sequence of the exchange operations will be less than 104.

Output

If Nick can increase his wealth, output YES, in other case output NO to the output file.

Sample Input

Sample Output

这是一个单源最短路 Bellman Ford算法的变形题,本题可以建立如下的图模型,以各种货币为顶点Vi,以货币间的每一种兑换方式为边Ei,然后就可以建立起来一个有向带权图。Bellman Ford算法参见 *这篇文章*  单源最短路参见此文,此题的要求 就是找出一个权值为正的环,这和Bellman Ford算法中的找负环是一个道理,我们只需要修改一下BellmanFord的松弛操作,改为每次都找从源点到该点的最大权值,并且将所有值初始为无穷小 (本题初始化为0即可) ,判断是否有负环 改为判断是否有正环,即可,当找到正环时,返回TRUE 否则返回FALSE。

代码如下

目前还有一个地方没有弄明白,就是那个flag为false就直接break 留下来一会儿研究

据说这个题还可以用SPFA 做,现在还不会 先留着以后看

单源最短路分析及算法实现

单源最短路分析及算法实现

最短路径的理解性解释:Va 到 Vb 的最短路的意义是 在一个带权图中,从节点Va到节点Vb的权值总和最小的路径 就是Va 到 Vb的最短路,这个权值可以是距离 时间 等各种量

理解最短路径首先要理解什么是最优子结构  最优子结构是在各种动态规划贪心以及最短路算法中都很关键的一个结构。  最优子结构的意思就是,问题局部的最优解包含在全局的最优解之中,这样才能把问题分成较小的问题先进行处理。

可以通过反证法证明,最短路问题是最优子结构,方法详见 算法导论第三版 P375

在计算最短路之前,还要考虑一个特殊情况,如果在图中存在负权值的边,就可能有一种比较特殊的情况了: 如果 图中存在负权值的边的话但不存在和的权值为负的环,那么 每一个路径的最短距离都可以精确求出,没有问题,不过,如果图中存在和为负权值的环,最短路就没有意义了  因为 总可以通过经过完整的一次环,来得到更小的一个权值 ,理论上 这个最短路径的大小为  -∞

求最短路的某些算法假设输入的边权值全为非负 如 Dijkstra算法,而还有一些算法只要没有负权值的环就可以 如 Bellman Ford算法 ,如果存在负权值的环的环也可以通过算法报告出来

先试试如何应用这个算法,再继续研究算法的正确性;                             //参考POJ 1860