poj 1094 Sorting It All Out 拓扑排序的唯一性问题

缘起

日常浪费生命 poj 1094 Sorting It All Out

分析

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
给你n个字母，有m个判断语句。求在哪个语句就可以判断出这个是不是一个环，或者在哪个语句可以判断出这些字母
的排序规则，或者就是不能确定。

【输入】
多样例. 每个样例一个N一个M. 2 <= n <= 26,m是正整数. 然后就是形如A<B这种关系 

【输出】
看样例

【样例输入】
4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0

【样例输出】
Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

【限制】
1s

其实就是拓扑序是否唯一的问题. 因为n较小. 所以可以 读入一组关系就重新进行一次拓扑排序.

而拓扑序唯一的充要条件是每次栈中的元素维持在1个.

还有就是本题的输入输出要控制好

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;
//#define LOCAL

int n,m, indeg[30], head[30], cnt, indegg[30], anstop;
char ccc[10],ans[30];

struct Arc
{
	int from, to, nxt;
}g[1000];

void addArc(int a, int b)
{
	g[cnt].from = a, g[cnt].to = b, g[cnt].nxt = head[a];
	head[a] = cnt++;
}

int topsort() // 返回-1表示存在环,返回0表示不确定(即拓扑序不唯一), 返回1表示拓扑序唯一存在
{
	anstop = 0;
	bool flag = false; // 拓扑排序过程中有没有出现过s中的元素多余1个的情形
	stack<int> s;
	int nn = n;
	memcpy(indegg, indeg, sizeof(indeg)); // 不能破坏原有的indeg, 只能拷贝一份出来
	for (int i = 1; i<=n;i++)
	{
		if (!indegg[i])
		{
			s.push(i);
		}
	}
	while(!s.empty())
	{
		if (s.size()>1)
		{
			flag = true; // 不能立刻返回0,因为可能存在环呢! 所以只能记录一下
		}
		int top = s.top();
		s.pop();
		ans[anstop++] = 'A'+top-1;
		nn--;
		for (int h = head[top],to; ~h; h = g[h].nxt)
		{
			to = g[h].to;
			if (!--indegg[to])
			{
				s.push(to);
			}
		}
	}
	if (nn)
	{
		return -1;
	}
	if (flag)
	{
		return 0;
	}
	ans[anstop] = 0;
	return 1;
}

int main() {

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%d%d", &n,&m), n&&m)
	{
		memset(indeg, 0, sizeof(indeg));
		memset(head, -1, sizeof(head));
		cnt = 0;
		getchar();
		bool ok = false; // 是不是已经得到确定性关系了? 毕竟得到确定性关系之后,本用例的数据还是要读完的
		for(int step = 1; step<=m; step++)
		{
			gets(ccc);
			if (ok)
			{
				continue; // 只消耗本样例数据
			}
			addArc(ccc[0]-'A'+1,ccc[2]-'A'+1);
			indeg[ccc[2]-'A'+1]++;
			int ret = topsort(); // 利用现有关系进行拓扑排序
			if (!~ret)
			{
				printf("Inconsistency found after %d relations.\n", step);
				ok = true;
			}
			else if (ret) // 唯一拓扑序确地了
			{
				printf("Sorted sequence determined after %d relations: %s.\n", step, ans);
				ok = true;
			}
		}
		if (!ok)
		{
			puts("Sorted sequence cannot be determined.");
		}
	}
	return 0;
}

ac情况

Status Accepted
Memory 112kB
Length 1840
Lang C++
Submitted 2019-09-08 08:54:42
Shared
RemoteRunId 20842551