学步园

Sorting It All Out
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 11772 Accepted: 3845

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.

这是一道很让人orz的题目。也许是小虾我水平太弱。。。。

代码写了3000b+

三种情况，判断的有点软乱，不过最后还是出来了，哈哈

总结一些拓扑排序的经验

1.如果队列中有超过一个的节点，那一定是不稳定的

2.如果由出度考虑，可以实现由小到大排列

3.如果到结束还没有判断出来，那么就是无法判断

4.如果当中成功了，下面的就不用管了。

A_C CODE

#include <iostream><br /> #include <algorithm><br /> #include <functional><br /> #include <queue><br /> #include <stdlib.h><br /> using namespace std;<br /> priority_queue<int>zero;<br /> int rise=0;<br /> int out[1001],outSize=0;<br /> int flagout[1001];<br /> class p{<br /> public: int rudu;<br /> int chudu;<br /> int v[1000];<br /> int len;<br /> bool vis;<br /> }point[1000],scrPoint[1000];<br /> int vis[1000],visPos=0;</p> <p>bool tflag=true;//出现zero.size为一<br /> int topo(int len)<br /> {<br /> if(zero.size()>1)<br /> tflag=false;<br /> if(zero.size()==0&&outSize==len&&tflag==true)<br /> return 0;//成功找到<br /> if(zero.size()==0&&outSize==visPos)<br /> return 1;//和当前的个数一样，不能确定<br /> if(zero.size()==0)<br /> return 2;//出现环</p> <p> int max=zero.top();<br /> out[outSize++]=max;</p> <p> zero.pop();<br /> for( int i=0 ; i<point[max].len ; i++ )<br /> {</p> <p> int tmpPos=point[max].v[i];</p> <p> rise++;</p> <p> point[tmpPos].rudu--;</p> <p> if( point[tmpPos].rudu==0 )</p> <p> {<br /> zero.push(tmpPos);<br /> }</p> <p> }</p> <p> topo(len);<br /> }<br /> void copy(int n)<br /> {<br /> for(int i=1;i<=n;i++)<br /> {<br /> point[i].chudu=scrPoint[i].chudu;<br /> point[i].rudu=scrPoint[i].rudu;</p> <p> }<br /> }<br /> int main()<br /> {<br /> int n,m;</p> <p> while(cin>>n>>m)<br /> {<br /> if(n==0&&m==0)<br /> return 0;<br /> int flag=0,outflag=0,iflag=true,iiflag=true;<br /> bool need=true;<br /> rise=0;<br /> int ask;<br /> outSize=0;<br /> memset(vis,0,sizeof(vis));<br /> for(int i=1;i<=n;i++)<br /> {<br /> point[i].chudu=scrPoint[i].chudu=0;<br /> point[i].rudu=scrPoint[i].rudu=0;<br /> point[i].len=scrPoint[i].len=0;<br /> point[i].vis=false;<br /> }</p> <p> char a,b,c;<br /> visPos=0;//当前没有节点<br /> for(int i=1;i<=m;i++)<br /> {<br /> rise=0;<br /> outSize=0;<br /> tflag=true;<br /> while(!zero.empty())<br /> {<br /> zero.pop();<br /> }<br /> //每加入一个新的数字，就判断一次<br /> getchar();<br /> scanf("%c%c%c",&a,&b,&c);<br /> a-='A'-1;<br /> c-='A'-1;<br /> if(!vis[a])//如果以前没有访问过，则加入队列<br /> {<br /> vis[a]=1;<br /> visPos++;<br /> }<br /> if(!vis[c])<br /> {<br /> vis[c]=1;<br /> visPos++;<br /> }<br /> if(b=='<')<br /> swap(a,c);</p> <p> scrPoint[a].rudu++;<br /> scrPoint[c].chudu++;<br /> point[c].v[point[c].len++]=a;//只改变长度</p> <p> copy(n);//使用scrPoint对前面的数据重新赋值</p> <p> for(int j=1;j<=n;j++)//对zero队列的初始化<br /> {<br /> if(point[j].rudu==0&&vis[j])//控制输入，如果没有出现过的vis为false<br /> {<br /> zero.push(j);<br /> rise++;<br /> }<br /> }<br /> flag=topo(n);//topo排序并对结果处理<br /> flagout[i]=flag;</p> <p> if(flag==0&&need==true)<br /> {outflag=flag;ask=i;need=false;}</p> <p> if(need==true)//need为真也是判断条件，因为题目意思如果前面的条件判断为真，后面为假也是真<br /> if(flag==2)<br /> {<br /> outflag=flag;ask=i;<br /> }</p> <p> }//大for循环结束，好大的一个for，下次总结应该写成函数<br /> for(int i=m-1;i>=1;i--)//如果在某点形成闭环了，在之后的情况下也会闭环，所以要寻找第一个闭环<br /> if(flagout[i]==2)<br /> {<br /> flag=2;<br /> ask=i;<br /> }<br /> else break;<br /> if(flag == 1)//循环到m还是无法判断<br /> cout<<"Sorted sequence cannot be determined."<<endl;<br /> else<br /> {<br /> if(outflag == 0)//outsize的长度正好为n,成功.</p> <p> {<br /> printf("Sorted sequence determined after %d relations: ",ask);//输出排列<br /> {<br /> for(int i=0;i<n-1;i++)<br /> printf("%c",out[i]+'A'-1);<br /> printf("%c",out[n-1]+'A'-1);<br /> cout<<"."<<endl;<br /> }<br /> }<br /> if(outflag==2)<br /> printf("Inconsistency found after %d relations./n",ask);</p> <p> }<br /> }<br /> }