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 Source East Central North America 2001 |
題目大意：
給出一些字母和它們之間的偏序關系，讓你來判斷通過這些關系是否能構成唯一的升序序列。如果能，輸出這個序列，并輸出是通過前多少關系得出的（即使之後的關系引出沖突也不必理會）。如果存在沖突，則輸出前多少項出現的沖突的。如果輸入完仍無法得出唯一關系，輸出相關資訊。
題目算法：
拓撲排序。
拓撲排序：若G包含有向邊(U,V)，則在序列中U出現在V之前，即該序列使得圖中所有有向邊均從左指向右。如果圖是有回路的，就不存在這樣的序列。
首先選擇一個無前驅的頂點(即入度為0的頂點，圖中至少應該有一個這樣的頂點，否則肯定存在回路)，然後從圖中移去該頂點以及由其發出的所有有向邊，如果圖中還存在無前驅的頂點，則重複上述操作，直到操作無法進行。如果圖不為空，說明圖中存在回路，無法進行拓撲排序；否則移出的頂點的順序就是對該圖的一個拓撲排序。
具體思路：
每輸入一組偏序關系進行一次拓撲排序。
如果存在回路，輸出沖突。
在不存在回路的基礎上，判斷每次入度為0的點是否唯一，隻有保證每次隻有一個點入度為0，才能保證最終的序列唯一。
注意：如果對于某一次輸入已經能确定序列沖突或者序列完全有序，則可以忽略後面的輸入。
當入度為0的定點大于1時，直接return了，但之後可能出現回路即沖突的情況。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
using namespace std;
int n,m,indeg[30],vis[30];
vector<int> vt[30];
char res[30];
int TopoSort(){
stack<int> st;
int flag=1;
for(int i=0;i<n;i++){
vis[i]=indeg[i];
if(indeg[i]==0)
st.push(i);
}
if(st.size()>1)
flag=0;
int cnt=0;
while(!st.empty()){
int u=st.top();
st.pop();
res[cnt++]=(char)u+'A';
for(int i=0;i<vt[u].size();i++)
if(--vis[vt[u][i]]==0)
st.push(vt[u][i]);
if(st.size()>1)
flag=0;
}
res[cnt]='\0';
for(int i=0;i<n;i++)
if(vis[i])
return -1;
return flag && (cnt==n);
}
int main(){
//freopen("input.txt","r",stdin);
char str[5];
int tag,flag,ans;
while(~scanf("%d%d",&n,&m)){
if(n==0 && m==0)
break;
memset(indeg,0,sizeof(indeg));
for(int i=0;i<n;i++)
vt[i].clear();
ans=tag=0;
for(int i=1;i<=m;i++){
scanf("%s",str);
vt[str[0]-'A'].push_back(str[2]-'A');
indeg[str[2]-'A']++;
if(tag==0){
flag=TopoSort();
if(flag==-1){
ans=i;
tag=-1;
}
if(flag==1){
ans=i;
tag=1;
}
}
}
if(tag==1)
printf("Sorted sequence determined after %d relations: %s.\n",ans,res);
else if(tag==-1)
printf("Inconsistency found after %d relations.\n",ans);
else if(tag==0)
printf("Sorted sequence cannot be determined.\n");
}
return 0;
} 1 #include<iostream>
2 #include<string>
3 #include<cstdio>
4 #include<cstring>
5
6 using namespace std;
7
8 int deg[30],d[30],g[30][30],res[30];
9 int n,m;
10
11 int Topo(string str){
12 int x=str[0]-'A';
13 int y=str[2]-'A';
14 if(g[x][y]==0){
15 g[x][y]=1;
16 d[y]++;
17 }
18 for(int i=0;i<n;i++)
19 deg[i]=d[i];
20 int flag=1,len=0,tmp,cnt;
21 for(int i=0;i<n;i++){
22 cnt=0;
23 for(int j=0;j<n;j++)
24 if(deg[j]==0){
25 tmp=j;
26 cnt++;
27 }
28 if(cnt==0)
29 return -1;
30 else if(cnt>1) //這裡不直接return 0;因為之後可能出現回路
31 flag=0;
32 deg[tmp]--;
33 res[len++]=tmp;
34 for(int j=0;j<n;j++)
35 if(g[tmp][j]==1)
36 deg[j]--;
37 }
38 return flag;
39 }
40
41 void Solve(){
42 string str;
43 int flag=1;
44 for(int i=0;i<m;i++){
45 cin>>str;
46 if(flag){
47 int tmp=Topo(str);
48 if(tmp==1){
49 cout<<"Sorted sequence determined after "<<i+1<<" relations: ";
50 for(int j=0;j<n;j++)
51 cout<<char(res[j]+'A');
52 cout<<"."<<endl;
53 flag=0;
54 }else if(tmp==-1){
55 cout<<"Inconsistency found after "<<i+1<<" relations."<<endl;
56 flag=0;
57 }
58 }
59 }
60 if(flag)
61 cout<<"Sorted sequence cannot be determined."<<endl;
62 }
63
64 int main(){
65
66 //freopen("input.txt","r",stdin);
67
68 string str;
69 while(scanf("%d%d",&n,&m)){
70 if(n==0 && m==0)
71 break;
72 if(n-1>m){
73 for(int i=0;i<m;i++)
74 cin>>str;
75 cout<<"Sorted sequence cannot be determined."<<endl;
76 continue;
77 }
78 memset(g,0,sizeof(g));
79 memset(d,0,sizeof(d));
80 Solve();
81 }
82 return 0;
83 }