杭电ACM1116——Play on Words~欧拉路径与欧拉回路

杭电ACM1116——Play on Words~~欧拉路径与欧拉回路

这一题，相比之前做的题目，增加了欧拉路径的求解。而且这一题是有向图。题目大概的意思就是成语接龙，能接起来就算可以打开门，因此要考虑两种，一种是回路，另外一种是一条路径。

第一次WR就是因为没有考虑回路这一个因素。

有向图中，欧拉回路与欧拉路径的求解方法：

1.欧拉回路：

首先当然是图连通，其次就是所以顶点的入度都等于出度。

2.欧拉路径：

首要的还是图连通，然后就是存在一个顶点的出度大入度1，存在一个顶点的入度大出度1，其他顶点的入度等于出度。

这些就不再证明。图的连通可以用DFS来判断或者并查集，个人喜欢并查集。

下面是AC的代码，有详细的注释：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int par[30], indegree[30], outdegree[30];    //par为并查集，indegree为入度，outdegree为出度
bool vis[30];                                //vis为该顶点出现过的标记
int finds(int x)                             //并查集的查找函数
{
	int r = x;
	while(r != par[r])
		r = par[r];
	int i = x, j;
	while(i != r)                            //路径压缩
	{
		j = par[i];
		par[i] = r;
		i = j;
	}
	return r;
}
void join(int x, int y)                      //并查集的合并函数
{
	int fx = finds(x);
	int fy = finds(y);
	if(fx != fy)
		par[fy] = fx;
}
int main()
{
	int t, n, i;
	char str[1005];
	scanf("%d", &t);
	while(t--)
	{
		memset(indegree, 0, sizeof(indegree));        //初始化各个数组
		memset(outdegree, 0, sizeof(outdegree));
		memset(vis, false, sizeof(vis));
		for(i = 0; i < 30; i++)                       //初始化并查集
			par[i] = i;
		scanf("%d", &n);
		while(n--)
		{
			scanf("%s", str);
			int len = strlen(str);
			join(str[0] - 'a', str[len - 1] - 'a');   //合并出现的顶点
			indegree[str[len - 1] - 'a']++;           //相应的入度+1
			outdegree[str[0] - 'a']++;                //相应的出度+1
			vis[str[0] - 'a'] = true;                 //标记该顶点出现过
			vis[str[len - 1] - 'a'] = true;
		}
		int flag = 0, tag = 0, a = 0, b = 0;          //flag来判图是否连通，tag为图中顶点入度不等于出度的个数
							<span style="white-space:pre">	</span>//a为入度大出度1的点的个数，b为出度大入度1的点的个数
		for(i = 0; i < 30; i++)                       //判连通
		{
			if(vis[i] && par[i] == i)
				flag++;
		}
		if(flag > 1)                                   //不连通，直接输出
		{
			printf("The door cannot be opened.\n");
		}
		else
		{
			for(i = 0; i < 30; i++)                    //查找tag，a， b 的个数
			{
				if(vis[i] && indegree[i] != outdegree[i])
				{
					tag++;
				}
				if(vis[i] && indegree[i] - outdegree[i] == 1)
					a++;
				if(vis[i] && outdegree[i] - indegree[i] == 1)
					b++;
			}
			if(tag == 0)                              //tag = 0，存在欧拉回路
				printf("Ordering is possible.\n");
			else if(a == b && a == 1 && tag == 2)     //a = 1 && b = 1 && tag = 2.存在欧拉路径
				printf("Ordering is possible.\n");
			else
				printf("The door cannot be opened.\n");
		}
	}
	return 0;
}