WA On Test 1
#include <bits/stdc++.h>
using namespace std;
const int N=26;
int n,m;
vector<int> g[N];
int vis[N],sz;
char seq[N];
bool flag;
bool dfs(int u){
vis[u]=1;
for(int v : g[u]){
if(vis[v]==1){
flag=1;
return 0;
}
else if(vis[v]==0){
if(!dfs(v))
return 0;
}
}
vis[u]=2;
seq[sz++]=(char)('A'+u);
return 1;
}
bool toposort(){
memset(vis,0,sizeof(vis));
sz=0;
flag=0;
for(int i=0;i<n;++i){
if(vis[i]==0){
if(!dfs(i))
return 0;
}
}
reverse(seq,seq+sz);
return 1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;++i){
char op,u,v;
cin>>u>>op>>v;
if(u==v){
cout<<"Inconsistency found after "<<i<<" relations."<<"\n";
return 0;
}
g[u-'A'].push_back(v-'A');
if(toposort()){
if(!flag){
bool ok=1;
int ind[N]={0};
int cnt=0;
for(int j=0;j<n;++j){
ind[j]=0;
for(int k=0;k<n;++k){
for(int nei : g[k]){
if(nei==j)
ind[j]++;
}
}
if(ind[j]==0) cnt++;
}
if(cnt>1) ok=0;
if(ok){
cout<<"Sorted sequence determined after "<<i<<" relations: ";
for(int j=0;j<sz;++j) cout<<seq[j];
cout<<"."<<"\n";
return 0;
}
}
}
else{
cout<<"Inconsistency found after "<<i<<" relations."<<"\n";
return 0;
}
}
cout<<"Sorted sequence cannot be determined.";
return 0;
}