一道拓扑的题,只是每增加一条拓扑一次,要注意是否有人为添加的边,也就是同一时刻有没有多个可选项。
这题少加了个return 0,错了n次……注意细节。
非常简单的题,结果写了70多分钟……
/* author:jxy lang:C/C++ university:China,Xidian University **If you need to reprint,please indicate the source** */ #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <queue> #define INF 1E9 using namespace std; bool vis[30]; int q[700]; int first[30],in[30],t[30]; int U[700],next[700],cnt; int m,n; void add(int v,int u) { in[u]++; next[cnt]=first[v]; first[v]=cnt; U[cnt++]=u; } char s[30]; int solve(int n) { memset(s,0,sizeof(s)); int top=-1,i,j,now,pos=0,c=0; bool flag=1; for(i=0;i<n;i++)//找到初始状态 { t[q[i]]=in[q[i]]; if(t[q[i]])continue; t[q[i]]=top;top=q[i]; c++; } for(i=0;i<n;i++) { if(c>1) flag=0;//如果c>1,代表有人为添加的序列 else if(c==0)return -1;//存在环 s[pos++]=top+'A'; c--; now=top;top=t[top]; for(j=first[now];j!=-1;j=next[j]) if(--t[U[j]]==0) { t[U[j]]=top; top=U[j]; c++; } } if(flag) return pos; return 0;//少加了这个return 0,错了n次…… } bool input() { scanf("%d%d",&n,&m); if(n==0&&m==0)return 0; memset(first,-1,sizeof(first)); memset(in,0,sizeof(in)); memset(vis,0,sizeof(vis)); cnt=0; int i,now=0,ans,pos,ff=0; char so[5]; for(i=0;i<m;i++) { scanf("%s",so);if(ff)continue; add(so[0]-'A',so[2]-'A'); if(vis[so[0]-'A']==0) vis[so[0]-'A']=1,q[now++]=so[0]-'A'; if(vis[so[2]-'A']==0) vis[so[2]-'A']=1;q[now++]=so[2]-'A'; ans=solve(now);//每增加一条一次拓扑 if(ans==-1){pos=i+1;ff=1;continue;} else if(ans==n){ff=1;pos=i+1;continue;} } if(ans==n) printf("Sorted sequence determined after %d relations: %s.\n",pos,s); else if(ans==-1) printf("Inconsistency found after %d relations.\n",pos); else printf("Sorted sequence cannot be determined.\n"); return 1; } int main() { while(input()); }