主题链接：
题目：
|
Sorting It All Out
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 Sample Output Sorted sequence determined after 4 relations: ABCD. Source |
这个题目对拓扑排序考虑的很细致。。
考虑了成环的情况。成环的情况也就是最后存在入度不为0的点。。
则计数后最后的num不等于n。。
这个题目还有就是这个题目不是对全部的信息进行综合推断，而是依据前面的假设可以得到已经成环了，或者可以得到n的大小顺序了，则后面的就不用推断了。。。所以用ok1，ok2两个变量进行控制。。
。
代码为：
#include<cstdio>
#include<stack>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=26+10;
int n,m;
int in[maxn],Copy[maxn],map[maxn][maxn],temp[maxn];
stack<int>S;
int topo()
{
int flag=0,num=0;
while(!S.empty()) S.pop();
memcpy(Copy,in,sizeof(in));
for(int i=0;i<n;i++)
{
if(Copy[i]==0)
S.push(i);
}
while(!S.empty())
{
if(S.size()>1)
flag=1;
int Gery=S.top();
S.pop();
temp[num++]=Gery;
for(int i=0;i<n;i++)
{
if(map[Gery][i])
{
if(--Copy[i]==0)
S.push(i);
}
}
}
if(num!=n)
return 0;//成环。则已经能够确定关系了，能够标记。
if(flag)
return 1;//有多个入度为0的点，则还不确定。继续输入信息。添加条件，看能否够得到顺序。
return 2;//顺序已经得到确定。能够标记。 } int main()
{
char str[maxn];
int ok1,ok2,u,v,i,is_n;
while(~scanf("%d%d",&n,&m),n,m)
{
is_n=0;
memset(in,0,sizeof(in));
memset(map,0,sizeof(map));
ok1=ok2=0;
for(i=1;i<=m;i++)
{
scanf("%s",str);
if(!ok1&&!ok2)
{
u=str[0]-'A';
v=str[2]-'A';
if(map[u][v]==0)
{
map[u][v]=1;
in[v]++;
}
int ans=topo();
if(ans==0)
{
is_n=i;
ok2=1;
}
else if(ans==2)
{
is_n=i;
ok1=1;
}
}
}
if(ok1)
{
printf("Sorted sequence determined after %d relations: ",is_n);
for(int i=0;i<n-1;i++)
printf("%c",temp[i]+'A');
printf("%c.\n",temp[n-1]+'A');
}
if(ok2)
printf("Inconsistency found after %d relations.\n",is_n);
if(ok1==0&&ok2==0)
printf("Sorted sequence cannot be determined.\n");
}
return 0;
}
版权声明：本文博客原创文章。博客，未经同意，不得转载。