测试点下载下来一样,过不了
#include<bits/stdc++.h>
using namespace std;
const int N=30;
int n,m;
int u,v;
bool vis[N];
vector<int> vec[N];
deque<int> deq;
int flr[N];
int in[N];
int tin[N];
int cnt[N];
int fl[N];
int path[N];
bool over = false;
int cti(char x){
return x-'A'+1;
}
char itc(int x){
return x+'A'-1;
}
int topsort(){
memset(cnt, 0, sizeof(cnt));
memset(fl, 0, sizeof(fl));
for(int i=1; i<=n; i++) tin[i] = in[i];
for(int i=1;i<=n;i++){
if(tin[i]==0){
deq.push_back(i);
cnt[1]++;//cnt用于储存位于当前位次的有几个;
fl[i]=1;//fl储存点在第几层;
}//首次只有第一位的点;
}
int nmb;
nmb=0;
while(!deq.empty()){
int a=deq.front();
deq.pop_front();
path[++nmb]=a;//nmb用来正常储存输出路径;
for(int i:vec[a]){
tin[i]--;
if(tin[i]==0){
deq.push_back(i);
fl[i]=fl[a]+1;
cnt[fl[i]]++;//从哪个点来,层数就从前一个加一;
}
}
}
int sumfl=0;
for(int i=1;i<=n;i++){//先找出共有几层;
sumfl=max(fl[i],sumfl);
}
// for(int i=1;i<=sumfl;i++){
// cout<< cnt[i] << ",";
// }
// cout << endl;
for(int i=1;i<=sumfl;i++){
if(cnt[i]>1) return 0;//如果有层的数量不为1,则说明有无法确定的关系;
}
bool f;
for(int i=1;i<=n;i++){
if(tin[i]!=0) f=true;
}
if(f){
return -1;
}
else return 1;
}
int main(){
// ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;i++){
char a,b,c;
cin>>a>>b>>c;
u=cti(a),v=cti(c);
vec[u].push_back(v);
in[v]++;
// cout << "in:";
// for(int i=1; i<=n; i++) cout << in[i] << ",";
// cout << endl;
int res = topsort();
// cout << "res:" << res << endl;
if(res==1){
cout<<"Sorted sequence determined after "<<i<<" relations: ";
for(int i=1;i<=n;i++){
cout<<itc(path[i]);
}
cout<<".";
// over = true;
return 0;
}
else if(res==-1){
cout<<"Inconsistency found after "<<i<<" relations.";
// over = true;
return 0;
}
}
cout<<"Sorted sequence cannot be determined.";
return 0;
}