## Sorting It All Out

``````//topologial order
//存图记录 入度 出度
//队列维护
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;

int aa,bb,flag,n,m,solve;
char x[10];
int a,b,map[30][30],indg[30];
int ans[30],cnt;
queue<int>q;

void init(){
aa=flag=solve=0;
cin>>n>>m;
for(int i=0; i<=30; i++) indg[i]=0;
}

void topo_ans(){
for(int i=0; i<n; i++){
int t=ans[i];
cout<<(char)(t+'A'-1)<<" ";
}
cout<<endl;
}

void topo(){
for(int i=1; i<=30; i++) ans[i]=0; cnt=0;
while (!q.empty()) q.pop();

for(int i=1; i<=n; i++)
if(indg[i]==0)
q.push(i);

while(!q.empty()){
int u=q.front();
ans[cnt++]=u;
q.pop();
for(int i=1; i<=n; i++){
if(map[u][i]){
indg[i]--;
if(indg[i]==0)    q.push(i);
}
}
}

}

void judge_circular(){

}

int main(){
while(1){
init();
if(n==0 && m==0) break;

for(int i=1; i<=m; i++){
aa++;
cin>>x;
a=x[0]-'A'+1;
b=x[2]-'A'+1;
if(map[a][b]==1) continue;
map[a][b]=1;
indg[b]++;
judge_circular();
if(flag) break;
solve=1;
}

if(!flag) topo();

if(solve==1){
cout<<"Sorted sequence determined after "<<bb<<" relations: ";
topo_ans();
}
if(solve==2){
cout<<"Inconsistency found after "<<aa<<" relations."<<endl;
}
if(solve==3){
cout<<"Sorted sequence cannot be determined."<<endl;
}

}
return 0;
}

/*

if(map[a][b]==1 && map[b][a]==1) {cout<<"Inconsistency found after "<<aa<<" relations."<<endl;flag=1;break;}

*/
``````

``````void topo(){
for(int i=1; i<=30; i++) ans[i]=0; cnt=0;
while (!q.empty()) q.pop();
for(int i=1; i<=n; i++)
if(indg[i]==0)
q.push(i);
while(!q.empty()){
int u=q.front();
ans[cnt++]=u;
q.pop();
for(int i=1; i<=n; i++){
if(map[u][i]){
indg[i]--;
if(indg[i]==0)    q.push(i);
}
}
}
}
``````

This site uses Akismet to reduce spam. Learn how your comment data is processed.