Sorting It All Out
Time Limit: 1000MS | Memory Limit: 10000K |
Total Submissions: 19834 | Accepted: 6784 |
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
East Central North America 2001
對前n個字母,輸入m組确定他們之間的大小關系,進而判斷有沒有唯一的序列。
第一種輸出,在前t(t<=m)已能确定一個序列
第二種:不能确定唯一的序列
第三種:不存在拓撲排序
思路:拓撲排序+floyd。先用拓撲排序判斷在目前情況下,有沒有環的存在,如果有環的存在則證明m組關系是有沖突的,
即可輸出3。若沒有環,那沒接下來就是判斷能否構成唯一的有序序列,用floyd傳遞閉包,如果能構成唯一的有序序列,
則頂點1~n,必分布着0~n-1個入度,才能保證0個入度的頂點排在第1位,1個入度的頂點排在第2位(因為隻有1個頂點比它大),
以此類推。有一點要注意下,就是要每輸入一次判斷一下,如果有輸出了,以後就隻輸入就好,不用第二次輸出。
源代碼:
#include<iostream>
using namespace std;
bool graph[30][30];
int n,m;
int path[30];
bool TopSort()
{
int i,j,k;
int indegree[30];
for(i=0;i<n;i++)
{
indegree[i]=0;
for(j=0;j<n;j++)
indegree[i] += graph[j][i];
//cout<<i<<":"<<indegree[i]<<endl;
}
for(k=0;k<n;k++)
{
for(i=0;i<n && indegree[i]!=0;i++);
if(i==n)
return false;
indegree[i] = -1;
path[k] = i;
for(j=0;j<n;j++)
indegree[j] -= graph[i][j];
}
return true;
}
bool Floyd()
{
int i,j,k;
bool map[30][30];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
map[i][j]=graph[i][j];
/*cout<<"1:"<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cout<<graph[i][j]<<" ";
cout<<endl;
}*/
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(i!=k && k!=j && map[i][k] && map[k][j])
map[i][j] = 1;
/*cout<<"2:"<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cout<<map[i][j]<<" ";
cout<<endl;
}*/
bool vis[30],finish=false;
memset(vis,false,sizeof(vis));
int totalIndegree = 0;
for(i=0;i<n;i++)
{
totalIndegree = 0;
for(j=0;j<n;j++)
totalIndegree += map[j][i];
//cout<<":"<<totalIndegree<<endl;
if(vis[totalIndegree])
return false;
vis[totalIndegree] = true;
}
return true;
}
int main()
{
char c1,c2,c3;
bool finish;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n == 0 && m == 0)
break;
finish = false;
memset(graph,0,sizeof(graph));
for(int i=1;i<=m;i++)
{
cin>>c1>>c2>>c3;
if(finish) continue; //if it finished before,just input the data and do nothing
int u = c1-'A';
int v = c3-'A';
if(graph[u][v] == true) continue; //this relationship have already existed!!!!
graph[u][v] = true;
if(TopSort() == 0) //TopSort firstly,if a loop exist,inconsistency found
{
finish = true; //set the flag finish as true
printf("Inconsistency found after %d relations.\n",i);
continue;
}
if(Floyd()) //judge..
{
finish = true;
printf("Sorted sequence determined after %d relations: ",i);
for(int j=0;j<n;j++)
printf("%c",'A'+path[j]);
cout<<"."<<endl;
continue;
}
}
if(!finish)
printf("Sorted sequence cannot be determined.\n");
}
}