http://poj.org/problem?id=1094
Sorting It All Out
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 24505 | Accepted: 8487 |
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.
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
【题解】：
拓扑排序到底就行，注意：
当遇到两个入度为0的情况，需要判断是否出现环
唉，不说了，代码写得真挫，乱七八糟，不过能AC
【code】：
/**
Judge Status:Accepted Memory:704K
Time:0MS Language:G++
Code Lenght:2296B Author:cj
*/ #include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm> #define N 30
#define M N*N
using namespace std; int map[N][N],mark[N],in[N],tin[N];
char anstr[N];
int n,flag; void init()
{
memset(map,,sizeof(map));
memset(mark,,sizeof(mark));
memset(in,,sizeof(in));
memset(tin,,sizeof(tin));
} int topCheck(int id) //拓扑排序
{
int i,cnt=,pos=-;
for(i=;i<;i++)
{
if(mark[i]&&!in[i])
{
cnt++;
pos=i;
}
}
if(cnt>) //当有多个入度为0的点
{
flag = ; //标记出现多个入度为0的点的情况
in[pos] = -;
anstr[id] = pos+'A';
for(i=;i<;i++)
{
if(map[pos][i]) in[i]--;
}
return topCheck(id+);
}
if(cnt==)
{
for(i=;i<;i++)
{
if(mark[i]&&in[i]>)
{
return ; //入度都大于0，出现了环
}
}
if(id!=n||flag) return ; //当排序到入度为0时，并且一直没有出现过多个入度为0的情况，则排序可以完成
anstr[id]='\0';
return ;
}
in[pos] = -;
anstr[id] = pos+'A';
for(i=;i<;i++)
{
if(map[pos][i]) in[i]--;
}
return topCheck(id+); //进入下一层拓扑排序
return ;
} int main()
{
int m;
while(~scanf("%d%d",&n,&m))
{
if(!n&&!m) break;
char xx[];
int i;
init();
int temp=,pos=;
for(i=;i<=m;i++)
{
scanf("%s",xx);
int x = xx[]-'A';
int y = xx[]-'A';
mark[x] = mark[y] = ;
tin[y]++;
map[x][y] = ;
memcpy(in,tin,sizeof(int)*);
if(temp!=) continue;
flag = ;
temp = topCheck();
pos = i;
}
if(temp==)
{
anstr[pos+i]='\0';
printf("Sorted sequence determined after %d relations: %s.\n",pos,anstr);
continue;
}
if(temp==)
{
printf("Inconsistency found after %d relations.\n",pos);
continue;
}
puts("Sorted sequence cannot be determined.");
}
return ;
}