首页 > 代码库 > Sorting It All Out

Sorting It All Out

2024-09-27 18:53:02   218人阅读

Description

An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.

Input

Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.

Output

For each problem instance, output consists of one line. This line should be one of the following three:

Sorted sequence determined after xxx relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.

where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.

Sample Input

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

Sample Output

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.


题解：题目有点没说清楚，输出顺序：1.假设前几个条件得出结果。输出第一个结果   2.矛盾结果在顺序不确定之前。

通常会卡在第二个上。


#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;

const int INF = 0x3fffffff;

int in[100];
int t[100];
bool map[100][100];
bool sflag;
bool iflag;
bool cflag;
bool flag;
char s[100];

void ok(int n,int m,int k)
{
	queue<int> q;
	for(int i = 0;i < n;i++)
	{
		t[i] = in[i];
		if(t[i] == 0)
		{
			q.push(i);
		}
	}
	int cnt = 0;
	bool f = true;
	while(!q.empty())
	{
		int x = q.front();
		q.pop();
		s[cnt++] = (char)(x + ‘A‘);
		t[x]--;
		if(!q.empty())
		{
			f = false;
		}
		for(int i = 0;i < n;i++)
		{
			if(map[x][i])
			{
				if(--t[i] == 0)
				{
					q.push(i);
				}
			}
		}
	}
	if(cnt == n && f)
	{
		sflag = true;
		flag = false;
		s[n] = ‘\0‘;
		return;
	}
	for(int i = 0;i < n;i++)
	{
		if(t[i] > 0)
		{
			iflag = true;
			flag = false;
		}
	}
}

int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m) != EOF && (n + m) != 0)
	{
		getchar();
		char a,e,b;
		memset(map,false,sizeof(map));
		memset(in,-1,sizeof(in));
		int res = 0;
		flag = true;
		sflag = false;
		cflag = false;
		iflag = false;
		if(1 == n && m == 0)
		{
			printf("Sorted sequence determined after 0 relations: A.\n");
			continue;
		}
		for(int i = 1;i <= m;i++)
		{
			scanf("%c%c%c",&a,&e,&b);
			if(in[b - ‘A‘] == -1)
			{
				in[b - ‘A‘] = 0;
			}
			if(in[a - ‘A‘] == -1)
			{
				in[a - ‘A‘] = 0;
			}
			if(!map[a - ‘A‘][b - ‘A‘])
			{
				map[a - ‘A‘][b - ‘A‘] = true;
				in[b - ‘A‘]++;
			}
			if(flag)
			{
				ok(n,m,i);
				res = i;
			}

			getchar();
		}
		
		if(sflag)
		{
			printf("Sorted sequence determined after %d relations: %s.\n",res,s);
		}
		else if(iflag)
		{
			printf("Inconsistency found after %d relations.\n",res);
		}
		else
		{
			printf("Sorted sequence cannot be determined.\n");
		}
	}
	
	
	return 0;
}


Sorting It All Out


联系
我们