Sorting It All Out
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions:39731 | Accepted: 13975 |
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.
Source
题意：
给定关于n个字母的对应优先级关系，问是否可以根据优先级对他们进行排序。并且要求输出是在第几组可以得出结果。
会有优先级不一致和无法排序的情况。
思路：
感觉这题数据很迷啊，m的范围都不给我都不好估计复杂度。
以及，要注意输出时候的句号。特别是可以sort的时候。
是一道传递闭包的问题，用邻接矩阵建图，如果$A<B$，则表示$A$到$B$有一条有向边，$g['A']['B'] = 1$
每次添加一个关系，使用一次floyd计算能否得出结果，或者是否出现不一致。
输出排序结果的时候，其实只需要比较每个点的入度，按照入度从大到小排序就行了。
因为最后的矩阵是一个传递闭包，最小的那个字母肯定小于其他所有字母，也就是说他这一行会有$n-1$个$1$
#include<iostream>
//#include<bits/stdc++.h>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<climits>
using namespace std;
typedef long long LL;
#define N 100010
#define pi 3.1415926535
#define inf 0x3f3f3f3f int n, m;
int g[][], tmpg[][]; int floyd()
{
for(int i = ; i < n; i++){
for(int j = ; j < n; j++){
tmpg[i][j] = g[i][j];
}
}
for(int k = ; k < n; k++){
for(int i = ; i < n; i++){
for(int j = ; j < n; j++){
tmpg[i][j] |= tmpg[i][k] & tmpg[k][j];
if(tmpg[i][j] == tmpg[j][i] && tmpg[i][j] == && i != j){
return -;
}
}
}
}
for(int i = ; i < n; i++){
for(int j = ; j < n; j++){
if(tmpg[i][j] == tmpg[j][i] && tmpg[i][j] == && i != j){
return ;
}
}
}
return ;
} struct node{
int deg;
char ch;
};
bool cmp(node a, node b)
{
return a.deg > b.deg;
} void print()
{
//int deg[30];
//memset(deg, 0, sizeof(deg));
node character[];
for(int i = ; i < n; i++){
character[i].deg = ;
character[i].ch = 'A' + i;
}
for(int i = ; i < n; i++){
for(int j = ; j < n; j++){
if(tmpg[i][j]){
character[i].deg++;
}
}
}
sort(character, character + n, cmp);
for(int i = ; i < n; i++){
printf("%c", character[i].ch);
}
printf(".\n"); /*queue<int>que;
for(int i = 0; i < n; i++){
printf("%d\n", deg[i]);
if(!deg[i]){
que.push(i);
break;
}
}
for(int i = 0; i < n; i++){
int x = que.front();que.pop();
printf("%c", x + 'A');
for(int k = 0; k < n; k++){
if(tmpg[k][x])deg[k]--;
if(!deg[k])que.push(k);
}
}*/
} int main()
{
while(scanf("%d%d", &n, &m) != EOF && n || m){
memset(g, , sizeof(g));
/*for(int i = 0; i < n; i++){
g[i][i] = 1;
}*/ int i;
bool dont = false;
for(i = ; i <= m; i++){
char a, b;
getchar();
scanf("%c<%c", &a, &b);
g[a - 'A'][b - 'A'] = ;
if(!dont){
int flag = floyd();
if(flag == -){
printf("Inconsistency found after %d relations.\n", i);
dont = true;
}
else if(flag == ){
printf("Sorted sequence determined after %d relations: ", i);
print();
dont = true;
}
}
}
if(i > m && !dont){
printf("Sorted sequence cannot be determined.\n");
}
}
return ;
}