题目:POJ1094
大致题意就是多组输入,输入n,m(可以视为n个点,有m个关系)m个关系在字母A-Z范围内,给你一些关系比如A<B,就认为A到B之间有条有向路,可以分三种情况:
1.当出现了一组关系使图出现了环,则输出“Inconsistency found after K1 relations” 其中的K1就是在第几个关系出现了环,后面的关系就可以忽略不处理了
2.当还未输入完给的关系就确定了,n个点的关系,则后面的关系就不用处理了,直接输出“Sorted sequence determined after K2 relations: (点关系的顺序).” K2是此时确定关系的点的个数;
3.当输入完给的关系,还未确定n个点的关系,则输出“Sorted sequence cannot be determined.”
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 #include <stdio.h> #include <string.h> char a[5 ];int pre[300 ][300 ];int vis[1000 ],b[1000 ],c[1000 ];int n,m;int tuopu () { int rem,FLAG=1 ; for (int i=0 ;i<n;i++) b[i]=vis[i]; int g=0 ; for (int i=0 ;i<n;i++) { int res=0 ; for (int j=0 ;j<n;j++) { if (b[j]==0 ){ res++; rem=j; } } if (res>1 ) { FLAG=-1 ; } if (res==0 ) return -2 ; b[rem]=-1 ; c[g++]=rem; for (int k=0 ;k<n;k++) if (pre[rem][k]) b[k]--; } return FLAG; } int main () { while (~scanf ("%d%d" ,&n,&m)&&(n+m)) { memset (vis,0 ,sizeof (vis)); memset (pre,0 ,sizeof (pre)); int ans=0 ; for (int i=0 ;i<m;i++) { scanf ("%s" ,a); if (ans) continue ; if (pre[a[0 ]-'A' ][a[2 ]-'A' ]==0 ) { pre[a[0 ]-'A' ][a[2 ]-'A' ]=1 ; vis[a[2 ]-'A' ]++; } int s=tuopu (); if (s==-2 ) { printf ("Inconsistency found after %d relations.\n" ,i+1 ); ans=1 ; } if (s==1 ) { printf ("Sorted sequence determined after %d relations: " ,i+1 ); for (int i=0 ;i<n;i++) printf ("%c" ,c[i]+'A' ); puts ("." ); ans=1 ; } } if (!ans) printf ("Sorted sequence cannot be determined.\n" ); } return 0 ; }