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

五月 7, 2015 VOID001 Comments 0 Comment

转自: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}也分别是两个强连通分量。

直接根据定义，用双向遍历取交集的方法求强连通分量，时间复杂度为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)为指向栈中节点的后向边(非横叉边)
}

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

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++程序

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

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++;

{

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的图论总结

HDU 1142 A Walk Through The Forest

十月 30, 2014 VOID001 Comments 0 Comment

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

5 6

1 3 2

1 4 2

3 4 3

1 5 12

4 2 34

5 2 24

7 8

1 3 1

1 4 1

3 7 1

7 4 1

7 5 1

6 7 1

5 2 1

6 2 1

Sample Output

2 4

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

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

Dijkstra算法学习

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

十月 26, 2014 VOID001 Comments 0 Comment

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:

Always shut open doors behind you immediately after passing through
Never open a closed door
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:

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).
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!
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

START 1 2
1

END
START 0 5
1 2 2 3 3 4 4

END
START 0 10
1 9
2
3
4
5
6
7
8
9

END
ENDOFINPUT

START 1 2

END

START 0 5

1 2 2 3 3 4 4

END

START 0 10

1 9

END

ENDOFINPUT

Sample Output

YES 1
NO
YES 10

YES 1

YES 10

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

/*************************************************************************
    > File Name: 1300.cpp
    > Author: VOID_133
    > ################### 
    > Mail: ################### 
    > Created Time: 2014年10月25日 星期六 00时31分24秒
 ************************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<ctime>
#include<set>
using namespace std;

const int maxn=25;
int deg[maxn];

int main(void)
{
	char s[50];
	char inpstr[5000];
	while(scanf("%s",s) && strcmp(s,"ENDOFINPUT"))
	{
		if(!strcmp(s,"END")) continue;
		memset(deg,0,sizeof(deg));
		int sumdeg=0;
		int n,m;				//m is the first room ,total has n rooms
		scanf("%d%d",&m,&n);
		//printf("START %d %dn",m,n);							//DBEUG
		getchar();				//Clear the Enter
		int nodenum=0;
		while(nodenum<n-1)
		{
			gets(inpstr);
			int len=strlen(inpstr);
			int inpnum=0;
			bool flag;
			//printf("%sn",s);
			for(int i=0;i<=len;i++)
			{
				//INPUT READIN
				if(inpstr[i]==' '|| inpstr[i]=='�')
				{
					deg[nodenum]++;
					deg[inpnum]++;
					inpnum=0;
				}
				else
				{
					//printf("CHAR %c",inpstr[i]
					inpnum=inpnum*10+inpstr[i]-'0';
				}
			}
			nodenum++;
		}
		gets(s);
		gets(s);
		//Read in  END String
		for(int i=0;i<n;i++)
		{
			printf("Deg[%d]=%dn",i,deg[i]);
		}
	}
	return 0;
}

/*************************************************************************

> File Name: 1300.cpp

> Author: VOID_133

> ###################

> Mail: ###################

> Created Time: 2014年10月25日星期六 00时31分24秒

************************************************************************/

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<vector>

#include<cstring>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<cstdlib>

#include<ctime>

#include<set>

using namespace std;

const int maxn=25;

int deg[maxn];

int main(void)

{

char s[50];

char inpstr[5000];

while(scanf("%s",s) && strcmp(s,"ENDOFINPUT"))

{

if(!strcmp(s,"END")) continue;

memset(deg,0,sizeof(deg));

int sumdeg=0;

int n,m; //m is the first room ,total has n rooms

scanf("%d%d",&m,&n);

//printf("START %d %dn",m,n); //DBEUG

getchar(); //Clear the Enter

int nodenum=0;

while(nodenum<n-1)

{

gets(inpstr);

int len=strlen(inpstr);

int inpnum=0;

bool flag;

//printf("%sn",s);

for(int i=0;i<=len;i++)

{

//INPUT READIN

if(inpstr[i]==' '|| inpstr[i]=='')

{

deg[nodenum]++;

deg[inpnum]++;

inpnum=0;

}

else

{

//printf("CHAR %c",inpstr[i]

inpnum=inpnum*10+inpstr[i]-'0';

}

nodenum++;

}

gets(s);

//Read in END String

for(int i=0;i<n;i++)

{

printf("Deg[%d]=%dn",i,deg[i]);

}

return 0;

}

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

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

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

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

/*************************************************************************
    > File Name: 1300.cpp
    > Author: VOID_133
    > ################### 
    > Mail: ################### 
    > Created Time: 2014年10月25日 星期六 00时31分24秒
 ************************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<ctime>
#include<set>
using namespace std;

const int maxn=25;
int deg[maxn];

int main(void)
{
	char s[50];
	char inpstr[5000];
	while(scanf("%s",s) && strcmp(s,"ENDOFINPUT"))
	{
		if(!strcmp(s,"END")) continue;
		memset(deg,0,sizeof(deg));
		int sumdeg=0;
		int n,m;				//m is the first room ,total has n rooms
		scanf("%d%d",&m,&n);
		//printf("START %d %dn",m,n);							//DBEUG
		getchar();				//Clear the Enter
		int nodenum=0;
		while(nodenum<n-1)
		{
			gets(inpstr);
			int len=strlen(inpstr);
			int inpnum=0;
			bool flag;
			//printf("%sn",s);
			for(int i=0;i<=len;i++)
			{
				//INPUT READIN
                                //if(inpstr[i]==' '|| inpstr[i]=='�' )  //WRONG CODE
				if(inpstr[i]==' '|| (inpstr[i]=='�' && len))   //CORRECTED
				{
					//printf("%d ",inpnum);
					deg[nodenum]++;
					deg[inpnum]++;
					inpnum=0;
				}
				else
				{
					//printf("CHAR %c",inpstr[i]
					inpnum=inpnum*10+inpstr[i]-'0';
				}
			}
			nodenum++;
		}
		//Read in  END String
		gets(s);
		gets(s);
		/*for(int i=0;i<n;i++)
		{
			printf("DEG[%d]=%dn",i,deg[i]);
		}*/
		bool isEuler=true;
		if(m==0)					//START FROM 0 and END to 0 NO ODD POINTS
		{
			for(int i=0;i<n;i++)
			{
				sumdeg+=deg[i];
				if(deg[i]%2)
				{
					isEuler=false;
					break;
				}
			}
		}
		else
		{
			for(int i=0;i<n;i++)
			{
				sumdeg+=deg[i];
				if(i==0 || i==m) continue;
				if(deg[i]%2)
				{
					isEuler=false;
					break;
				}
			}
			if(!(deg[0]%2 && deg[m]%2))
			{
				isEuler=false;
			}
		}
		if(isEuler) printf("YES %dn",sumdeg/2);
		else printf("NOn");
	}
	return 0;
}

100

101

102

103

104

105

106

/*************************************************************************

> File Name: 1300.cpp

> Author: VOID_133

> ###################

> Mail: ###################

> Created Time: 2014年10月25日星期六 00时31分24秒

************************************************************************/

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<vector>

#include<cstring>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<cstdlib>

#include<ctime>

#include<set>

using namespace std;

const int maxn=25;

int deg[maxn];

int main(void)

{

char s[50];

char inpstr[5000];

while(scanf("%s",s) && strcmp(s,"ENDOFINPUT"))

{

if(!strcmp(s,"END")) continue;

memset(deg,0,sizeof(deg));

int sumdeg=0;

int n,m; //m is the first room ,total has n rooms

scanf("%d%d",&m,&n);

//printf("START %d %dn",m,n); //DBEUG

getchar(); //Clear the Enter

int nodenum=0;

while(nodenum<n-1)

{

gets(inpstr);

int len=strlen(inpstr);

int inpnum=0;

bool flag;

//printf("%sn",s);

for(int i=0;i<=len;i++)

{

//INPUT READIN

//if(inpstr[i]==' '|| inpstr[i]=='' ) //WRONG CODE

if(inpstr[i]==' '|| (inpstr[i]=='' && len)) //CORRECTED

{

//printf("%d ",inpnum);

deg[nodenum]++;

deg[inpnum]++;

inpnum=0;

}

else

{

//printf("CHAR %c",inpstr[i]

inpnum=inpnum*10+inpstr[i]-'0';

}

nodenum++;

}

//Read in END String

gets(s);

/*for(int i=0;i<n;i++)

{

printf("DEG[%d]=%dn",i,deg[i]);

}*/

bool isEuler=true;

if(m==0) //START FROM 0 and END to 0 NO ODD POINTS

{

for(int i=0;i<n;i++)

{

sumdeg+=deg[i];

if(deg[i]%2)

{

isEuler=false;

break;

}

else

{

for(int i=0;i<n;i++)

{

sumdeg+=deg[i];

if(i==0 || i==m) continue;

if(deg[i]%2)

{

isEuler=false;

break;

}

if(!(deg[0]%2 && deg[m]%2))

{

isEuler=false;

}

if(isEuler) printf("YES %dn",sumdeg/2);

else printf("NOn");

}

return 0;

}

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

十月 23, 2014 VOID001 Comments 0 Comment

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

并查集算法如下：

int findroot(int i)									//Search for the connected root of this node
{
	if(father[i]!=i)
	{
		father[i]=findroot(father[i]);
	}
	return father[i];
}

void unionNode(int a,int b)							//Union the two nodes
{
	int x,y;
	x=findroot(a);
	y=findroot(b);
	if(x!=y) father[x]=y;
	return ;
}

int findroot(int i) //Search for the connected root of this node

{

if(father[i]!=i)

{

father[i]=findroot(father[i]);

}

return father[i];

}

void unionNode(int a,int b) //Union the two nodes

{

int x,y;

x=findroot(a);

y=findroot(b);

if(x!=y) father[x]=y;

return ;

}

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

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

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

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

/*************************************************************************
    > File Name: 1116.cpp
    > Author: VOID_133
    > ################### 
    > Mail: ################### 
    > Created Time: 2014年10月23日 星期四 20时55分13秒
	> Comment:并查集&欧拉路  具体见blog
 ************************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<ctime>
#include<set>
using namespace std;

const int maxn=26;
int father[maxn];

int findroot(int i)									//Search for the connected root of this node
{
	if(father[i]!=i)
	{
		father[i]=findroot(father[i]);
	}
	return father[i];
}

void unionNode(int a,int b)							//Union the two nodes
{
	int x,y;
	x=findroot(a);
	y=findroot(b);
	if(x!=y) father[x]=y;
	return ;
}

int main(void)
{
	int in[maxn],out[maxn];							//Keep the indegree and outdegree
	int visit[maxn];
	char word[1005];
	int T;
	int cnt=0;
	bool isEulerLoop;
	bool isEulerPath;
	scanf("%d",&T);
	while(T--)
	{
		memset(in,0,sizeof(in));
		memset(out,0,sizeof(out));
		memset(visit,0,sizeof(visit));
		int n;
		scanf("%d",&n);
		for(int i=0;i<maxn;i++)
		{
			father[i]=i;
		}
		cnt=0;
		while(n--)
		{
			scanf("%s",word);
			int a=word[0]-'a';
			int b=word[strlen(word)-1]-'a';
			visit[a]=visit[b]=1;
			unionNode(a,b);
			out[a]++;
			in[b]++;
		}
		for(int i=0;i<maxn;i++)
		{
			father[i]=findroot(i);								//Find the roots 
		}
		/*//DEBUG
		printf("nDEBUG FATHERSn");
		for(int i=0;i<maxn;i++)
		{
			printf("father[%d]=%dn",i,father[i]);
		}
		printf("nDEBUG INn");
		for(int i=0;i<maxn;i++)
		{
			printf("in[%d]=%dn",i,in[i]);
		}
		printf("nDEBUG OUTn");
		for(int i=0;i<maxn;i++)
		{
			printf("out[%d]=%dn",i,out[i]);
		}
		//END DEBUG*/
		for(int i=0;i<maxn;i++)								//How to judge it only has one root
		{
			if(father[i]==i && visit[i])
				cnt++;
		}
		if(cnt!=1)
		{
			printf("The door cannot be opened.n");
		}
		else
		{
			isEulerLoop=true;
			isEulerPath=true;
			for(int i=0;i<maxn;i++)
			{
				if(in[i]!=out[i]) 
				{
					isEulerLoop=false;
				}
			}
			if(!isEulerLoop)
			{
				//Judge if it's Euler Path;
				int flaga=0;
				int flagb=0;
				for(int i=0;i<maxn;i++)
				{
					if(in[i]!=out[i])
					{
						if(in[i]-out[i]==1) flaga++;
						else if(out[i]-in[i]==1) flagb++;
						else
						{
							isEulerPath=false;
							break;
						}
					}
				}
				if(flaga!=1 || flagb!=1) isEulerPath=false;
			}
			if(isEulerLoop)
			{
				printf("Ordering is possible.n");
			}
			else if(isEulerPath)
			{
				printf("Ordering is possible.n");
			}
			else
			{
				printf("The door cannot be opened.n");
			}
		}
	}
	return 0;
}

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

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

/*************************************************************************

> File Name: 1116.cpp

> Author: VOID_133

> ###################

> Mail: ###################

> Created Time: 2014年10月23日星期四 20时55分13秒

> Comment:并查集&欧拉路具体见blog

************************************************************************/

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<vector>

#include<cstring>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<cstdlib>

#include<ctime>

#include<set>

using namespace std;

const int maxn=26;

int father[maxn];

int findroot(int i) //Search for the connected root of this node

{

if(father[i]!=i)

{

father[i]=findroot(father[i]);

}

return father[i];

}

void unionNode(int a,int b) //Union the two nodes

{

int x,y;

x=findroot(a);

y=findroot(b);

if(x!=y) father[x]=y;

return ;

}

int main(void)

{

int in[maxn],out[maxn]; //Keep the indegree and outdegree

int visit[maxn];

char word[1005];

int T;

int cnt=0;

bool isEulerLoop;

bool isEulerPath;

scanf("%d",&T);

while(T--)

{

memset(in,0,sizeof(in));

memset(out,0,sizeof(out));

memset(visit,0,sizeof(visit));

int n;

scanf("%d",&n);

for(int i=0;i<maxn;i++)

{

father[i]=i;

}

cnt=0;

while(n--)

{

scanf("%s",word);

int a=word[0]-'a';

int b=word[strlen(word)-1]-'a';

visit[a]=visit[b]=1;

unionNode(a,b);

out[a]++;

in[b]++;

}

for(int i=0;i<maxn;i++)

{

father[i]=findroot(i); //Find the roots

}

/*//DEBUG

printf("nDEBUG FATHERSn");

for(int i=0;i<maxn;i++)

{

printf("father[%d]=%dn",i,father[i]);

}

printf("nDEBUG INn");

for(int i=0;i<maxn;i++)

{

printf("in[%d]=%dn",i,in[i]);

}

printf("nDEBUG OUTn");

for(int i=0;i<maxn;i++)

{

printf("out[%d]=%dn",i,out[i]);

}

//END DEBUG*/

for(int i=0;i<maxn;i++) //How to judge it only has one root

{

if(father[i]==i && visit[i])

cnt++;

}

if(cnt!=1)

{

printf("The door cannot be opened.n");

}

else

{

isEulerLoop=true;

isEulerPath=true;

for(int i=0;i<maxn;i++)

{

if(in[i]!=out[i])

{

isEulerLoop=false;

}

if(!isEulerLoop)

{

//Judge if it's Euler Path;

int flaga=0;

int flagb=0;

for(int i=0;i<maxn;i++)

{

if(in[i]!=out[i])

{

if(in[i]-out[i]==1) flaga++;

else if(out[i]-in[i]==1) flagb++;

else

{

isEulerPath=false;

break;

}

if(flaga!=1 || flagb!=1) isEulerPath=false;

}

if(isEulerLoop)

{

printf("Ordering is possible.n");

}

else if(isEulerPath)

{

printf("Ordering is possible.n");

}

else

{

printf("The door cannot be opened.n");

}

return 0;

}

POJ 1860 Currency Exchange

九月 20, 2014 VOID001 Comments 0 Comment

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 R_AB, C_AB, R_BA and C_BA – 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<=10³.
For each point exchange rates and commissions are real, given with at most two digits after the decimal point, 10^-2<=rate<=10², 0<=commission<=10².
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 10⁴.

Output

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

Sample Input

3 2 1 20.0
1 2 1.00 1.00 1.00 1.00
2 3 1.10 1.00 1.10 1.00

3 2 1 20.0

1 2 1.00 1.00 1.00 1.00

2 3 1.10 1.00 1.10 1.00

Sample Output

YES

YES

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

代码如下

/*************************************************************************
    > File Name: 1860.cpp
    > Author: VOID_133
    > ################### 
    > Mail: ################### 
    > Created Time: 2014年09月20日 星期六 20时02分35秒
 ************************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<ctime>
#include<set>
using namespace std;

const int maxn=300;
typedef struct edge{
	int a;
	int b;
	double r;
	double c;

}Edge;

double dis[maxn];

Edge E[maxn];
int N,M,S;
double V;

int tot=0;
bool bellman_ford()
{
	dis[S]=V;
	for(int i=1;i<=N-1;i++)
	{
		bool flag=false;
		for(int j=0;j<tot;j++)
		{
			double tmp=(dis[E[j].a]-E[j].c)*E[j].r;
			if(dis[E[j].b]<tmp)
			{
				flag=1;
				dis[E[j].b]=tmp;
			}
		}
		if(!flag) break;
	}

	for(int j=0;j<tot;j++)
	{
		double tmp=(dis[E[j].a]-E[j].c)*E[j].r;
		if(dis[E[j].b]<tmp)
			return true;
	}
	return false;
}

int main(void)
{
	int ta,tb;
	double rab,cab,rba,cba;
	while(scanf("%d%d%d%lf",&N,&M,&S,&V)!=EOF)
	{
		tot=0;
		memset(E,0,sizeof(E));
		for(int i=0;i<M;i++)
		{
			scanf("%d%d%lf%lf%lf%lf",&ta,&tb,&rab,&cab,&rba,&cba);
			E[tot].a=ta;
			E[tot].b=tb;
			E[tot].r=rab;
			E[tot++].c=cab;
			E[tot].a=tb;
			E[tot].b=ta;
			E[tot].r=rba;
			E[tot++].c=cba;
		}
		if(bellman_ford())
		{
			cout<<"YES"<<endl;
		}
		else
		{
			cout<<"NO"<<endl;
		}
	}
	return 0;
}

/*************************************************************************

> File Name: 1860.cpp

> Author: VOID_133

> ###################

> Mail: ###################

> Created Time: 2014年09月20日星期六 20时02分35秒

************************************************************************/

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<vector>

#include<cstring>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<cstdlib>

#include<ctime>

#include<set>

using namespace std;

const int maxn=300;

typedef struct edge{

int a;

int b;

double r;

double c;

}Edge;

double dis[maxn];

Edge E[maxn];

int N,M,S;

double V;

int tot=0;

bool bellman_ford()

{

dis[S]=V;

for(int i=1;i<=N-1;i++)

{

bool flag=false;

for(int j=0;j<tot;j++)

{

double tmp=(dis[E[j].a]-E[j].c)*E[j].r;

if(dis[E[j].b]<tmp)

{

flag=1;

dis[E[j].b]=tmp;

}

if(!flag) break;

}

for(int j=0;j<tot;j++)

{

double tmp=(dis[E[j].a]-E[j].c)*E[j].r;

if(dis[E[j].b]<tmp)

return true;

}

return false;

}

int main(void)

{

int ta,tb;

double rab,cab,rba,cba;

while(scanf("%d%d%d%lf",&N,&M,&S,&V)!=EOF)

{

tot=0;

memset(E,0,sizeof(E));

for(int i=0;i<M;i++)

{

scanf("%d%d%lf%lf%lf%lf",&ta,&tb,&rab,&cab,&rba,&cba);

E[tot].a=ta;

E[tot].b=tb;

E[tot].r=rab;

E[tot++].c=cab;

E[tot].a=tb;

E[tot].b=ta;

E[tot].r=rba;

E[tot++].c=cba;

}

if(bellman_ford())

{

cout<<"YES"<<endl;

}

else

{

cout<<"NO"<<endl;

}

return 0;

}

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

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

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

九月 20, 2014 VOID001 Comments 0 Comment

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

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

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

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

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

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

VOID001's WOWO

✵Merry Christmas✵ Aim at being kernel hacker, now a newbie

Browsed by
分类：GraphTheory

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

五月 7, 2015 VOID001 Comments 0 Comment

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

[有向图强连通分量]

[Tarjan算法]

HDU 1142 A Walk Through The Forest

十月 30, 2014 VOID001 Comments 0 Comment

Problem Description

A Walk Through the Forest

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

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

十月 26, 2014 VOID001 Comments 0 Comment

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

十月 23, 2014 VOID001 Comments 0 Comment

Problem Description

Play on Words

POJ 1860 Currency Exchange

九月 20, 2014 VOID001 Comments 0 Comment

Currency Exchange

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

九月 20, 2014 VOID001 Comments 0 Comment