1090 - 确定排序序列
时间限制 : 1 秒
内存限制 : 32 MB
一个由不同的值组成的按升序排序的序列，通常使用小于操作符，把元素从小到大排列。
例如，有序序列A，B，C，D表示A<B，B<C和C<D。
现给你一组形如A<B的关系，请你确定是否已经形成一个排序的序列。
题目输入
输入包含多组测试数据。每组输入的第一行是两个正整数n和m。
n表示排序对象的个数，2<=n<=26。排序对象是字母表开始的n个大写字符。
m表示形如A<B的关系的个数。
接下来m行，每行输入一个关系，由三个字符构成：第一个大写字母，符号“<”，第二个大写字母。字母不会超过字母表开始的n个字母的范围。
当n=m=0时，输入结束。
题目输出
对于每组输入，输出一行。该行将是以下三者之一：
Sorted sequence determined after xxx relations: yyy...y.（在xxx个关系后，确定了排序序列：yyy...y）
Sorted sequence cannot be determined.（不能确定排序序列）
Inconsistency found after xxx relations.（在xxx个关系后，发现关系矛盾）
解释说明：
xxx是处理关系时，确定排序序列已经形成或发现关系矛盾时的关系数目，哪种情况先出现，就输出哪种。yyy...y是排序的升序序列。
输入/输出样例
输入格式
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
输出格式
Sorted sequence determined after 4 relations: ABCD. Inconsistency found after 2 relations. Sorted sequence cannot be determined.
C语言解答
#include<stdio.h> #include<string.h> #include<stdlib.h> int c[26],ar[26]; int map[26][26]; int n,m,mark; void search(int i,int max,int count,int arr[]) { int j; if(count==n&&mark==0) { for(j=0;j<=max;j++) ar[j]=arr[j]; mark=1; } else { for(j=0;j<=max;j++) if(map[i][j]==1) { arr[count]=j; search(j,max,count+1,arr); } } } int main() { int t,e,a,b,k,i,j,s,max,tag,loc; int arr[26]; char ord[4]; char al[26]="ABCDEFGHIJKLMNOPQRSTUVWXYZ"; while(scanf("%d%d",&n,&m)!=EOF&&m!=0&&n!=0) { for(i=0;i<26;i++) memset(map[i],0,26*sizeof(int)); memset(c,0,26*sizeof(int)); memset(arr,0,26*sizeof(int)); memset(ar,0,26*sizeof(int)); for(mark=tag=max=i=0;i<m;i++) { scanf("%s",&ord); a=ord[0]-'A';b=ord[2]-'A'; map[a][b]=1; c[b]=1; if(tag==0&&map[b][a]==1) { loc=i+1; tag=1; } if(b>max) max=b; if(a>max) max=a; if(tag==0) { for(k=j=0;j<=max;j++) if(c[j]==0) k++; if(k==0) { loc=i+1; tag=1; } } if(max==n-1&&tag==0) { for(j=0;j<=max;j++) if(c[j]==0) break; arr[0]=j; search(j,max,1,arr); if(mark==1) { loc=i+1; tag=2; } } } if(tag==0) printf("Sorted sequence cannot be determined.\n"); else if(tag==1) printf("Inconsistency found after %d relations.\n",loc); else { printf("Sorted sequence determined after %d relations: ",loc); for(k=0;k<=max;k++) printf("%c",al[ar[k]]); printf(".\n"); } } return 0; }
C++解答
#include<cstdio> #include<cstring> #include<vector> #include<queue> using namespace std; int n,m,pi[26],vis[26]; struct node { vector<int> adj[26]; int indeg[26]; }p; void add(node &N,int u,int v) { N.adj[u].push_back(v); N.indeg[v]++; } int toposort(node N) { int count=0,i,k=0,vn=0,bj=0; queue<int> q; for(i=0;i<n;i++) { if(vis[i]) { vn++; if(!N.indeg[i]) q.push(i); } } while(!q.empty()) { count++; int x=q.front(); q.pop(); pi[k++]=x; if(!q.empty()) bj=1; for(vector<int>::iterator it=N.adj[x].begin();it!=N.adj[x].end();it++) if(!(--N.indeg[*it])) q.push(*it); } if(vn==n) { if(count==n) { if(bj) return -1; else return 1; } else return 0; } else { if(count==vn) return -1; else return 0; } } int main() { int i,u,v,flag; char s[4]; while(scanf("%d%d",&n,&m)!=EOF,n||m) { flag=0; for(i=0;i<26;i++) { p.adj[i].clear(); p.indeg[i]=0; } memset(vis,0,sizeof(vis)); for(i=0;i<m;i++) { scanf("%s",s); u=s[0]-'A'; v=s[2]-'A'; vis[u]=vis[v]=1; add(p,u,v); if(!flag) { int t=toposort(p); if(t==0) { printf("Inconsistency found after %d relations.\n",i+1); flag=1; } else if(t==-1&&i==m-1) printf("Sorted sequence cannot be determined.\n"); else if(t==1) { printf("Sorted sequence determined after %d relations: ",i+1); for(int j=0;j<n;j++) printf(j==n-1?"%c.\n":"%c",pi[j]+'A'); flag=1; } } } } return 0; }