这题挺悲催的,RE了十几次,但最终被我发现了,哎,数据处理竟然出问题了。。。
回到题目吧,这题因为要判断在输入第几个语句后,是矛盾还是可以确定顺序,所以不能一次建完树,然后拓扑。
我的做法是每输入一条语句就在已建的树上修改,然后拓扑一次,直到可以得到结论(此处我竟然直接break了,然后一直RE,真是低级的错误,以后一定引以为戒!)
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int vs[30][30];//vs[i][j]比较i和j的大小,i<j:-1,i>j:1 int ans[30],top;//存储拓扑序列 bool flag[30]; int n,m; //拓扑 void dfs(int u) { flag[u]=true; for(int i=0;i<n;i++) if(!flag[i]&&vs[u][i]==-1) dfs(i); ans[top++]=u; } int main() { int i,j,k,t,a,b,cnt; char tmp[5]; bool ok; while(scanf("%d%d",&n,&m),n+m) { memset(vs,0,sizeof(vs)); memset(flag,false,sizeof(flag)); cnt=0; ok=false; for(k=1;k<=m;k++)//对于矛盾和可以确定顺序了,切记不能直接break { scanf("%s",tmp); if(ok) continue; a=tmp[0]-65; b=tmp[2]-65; if(!flag[a]) { cnt++; flag[a]=true; } if(!flag[b]) { cnt++; flag[b]=true; } if(vs[a][b]==-1)//无效边 continue; if(vs[a][b]==1)//矛盾边 { printf("Inconsistency found after %d relations.\n",k); ok=true; continue; } //修改树 vs[a][b]=-1; vs[b][a]=1; for(i=0;i<n;i++) for(j=0;j<n;j++) for(t=0;t<n;t++) { if(vs[i][t]==-1&&vs[t][j]==-1) vs[i][j]=-1; if(vs[i][t]==1&&vs[t][j]==1) vs[i][j]=1; } //各字母都出现了,才拓扑一下,否则没必要 if(cnt==n) { top=0; memset(flag,false,sizeof(flag)); for(i=0;i<n;i++) { if(!flag[i]) dfs(i); } for(i=1;i<n;i++) if(vs[ans[i]][ans[i-1]]!=-1) break; if(i==n)//可以确定顺序了 { ok=true; printf("Sorted sequence determined after %d relations: ",k); for(i=n-1;i>=0;i--) printf("%c",(char)(ans[i]+65)); printf(".\n"); } } } if(!ok) printf("Sorted sequence cannot be determined.\n"); } return 0; }