Uva 10129

跟Uva 10054很像,不过这题的单词是不能反向的,所以是有向图,判断欧拉道路。

关于欧拉道路(from Titanium大神):

判断有向图是否有欧拉路
1.判断有向图的基图(即有向图转化为无向图)连通性,用简单的DFS即可。如果图都不连通,一定不存在欧拉路
2.在条件1的基础上
  对于欧拉回路,要求苛刻一点,所有点的入度都要等于出度,那么就存在欧拉回路了
  对于欧拉道路,要求松一点,只有一个点,出度比入度大1,这个点一定是起点; 一个点,入度比出度大1,这个点一定是终点.其余点的出度等于入度
 (注意,只能大1,而且这样的点分别只能有1个,而且存在起点就一定要存在终点,存在终点就一定要存在起点)

他用判断连通性用的是DFS,我用的是并查集实现。

然后判断为欧拉回路(入度=出度)或者欧拉道路(出入度相差1的点只有不同的两个)(而且其他点出度=入度!)。


代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
const int maxn = 30;
int f[maxn], g[maxn][maxn], id[maxn], od[maxn];
int t, n, root;

int Find(int x) {
	if (x != f[x]) 
		return f[x] = Find(f[x]);
	return x;
}

int main () {
	scanf("%d", &t);
	while (t--) {
		char word[1001];
		scanf("%d", &n);
		for (int i = 0; i < maxn; i++) {
			f[i] = i;
			id[i] = 0;
			od[i] = 0;
			for (int j = 0; j < maxn; j++)
				g[i][j] = 0;
		}
		for (int i = 0; i < n; i++) {
			scanf("%s", word);
			int a = word[0] - 'a', b = word[strlen(word) - 1] - 'a';
			g[a][b]++;
			od[a]++;
			id[b]++;
			f[Find(a)] = Find(b);
			root = Find(b);
		}
		int i, ans = 0, flag = 1, in = 0, on = 0;
		for (i = 0; i < maxn; i++)
		if (id[i] || od[i]) {
			if (Find(f[i]) != root)
				ans++;
			if (id[i] - od[i] == 1)
				in++;
			else if (od[i] - id[i] == 1)
		 		on++;
			else if (abs(id[i] - od[i]) > 1)
				break;
		}
//		printf("%d %d %d %d
", i, ans, in, on);
		if (i < maxn || ans > 0 || in > 1 || on > 1)
			printf("The door cannot be opened.
");
		else
			printf("Ordering is possible.
");
	}//while
	return 0;
}


原文地址:https://www.cnblogs.com/java20130723/p/3212238.html