Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 分享两组关键性数据:

Posted by MyTalent at 2013-05-08 23:24:07 on Problem 1094
6 6
A<F
B<D
C<E
F<D
D<E
E<F
output：
Inconsistency found after 6 relations.

5 5
A<B
B<C
C<D
D<E
E<A
output:
Sorted sequence determined after 4 relations: ABCDE

#include <cstdio>
#include <cstring>
#define rep(i,repstt,repend) for(int i=repstt;i<repend;i++)
#define INIT(a,b) memset(a,b,sizeof(a))
int into[30],ans[30],n,m;
char tmpa,tmpb;
bool f[30][30];
int topo_sort(int sz,int work){
INIT(into,0);
rep(i,0,sz)rep(j,0,sz)
if(f[i][j])
into[j]++;
rep(i,0,sz){
rep(j,0,sz)
if(!into[j]){
ok++;
}
if(!ok)
return 0;
if(work==1&&ok>1)
return -1;
rep(k,0,sz)
into[k]--;
}
return 1;
}
int main(){
int res,i;
while(scanf("%d%d",&n,&m)&&(n+m)){
bool ud=1;
INIT(f,0);
for(i=0;i<m;i++){
scanf(" %c %*c %c",&tmpa,&tmpb);
f[tmpa-'A'][tmpb-'A']=1;
res=topo_sort(n,0);
if(res)//二次测试
res=topo_sort(n,1);
if(res==1){
printf("Sorted sequence determined after %d relations: ",i+1);
rep(j,0,n)putchar(ans[j]+'A');
printf(".\n");
rep(j,i+1,m)scanf(" %*c %*c %*c");
ud=0;
break;
}else if(!res){
printf("Inconsistency found after %d relations.\n",i+1);
rep(j,i+1,m)scanf(" %*c %*c %*c");
ud=0;
break;
}
}
if(ud)printf("Sorted sequence cannot be determined.\n");
}
}

Followed by: