#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int Maxn = 30,Maxm = 1e3;
int n,m;
int indeg[Maxn];
int indeg_[Maxn];
char result[Maxn];
int c2i(char ch){
return ch - 'A' + 1;
}
int head[Maxn];
struct Side{
int e;
int next;
}side[Maxm];
void add(int start,int end,int x){
side[x].e = end;
side[x].next = head[start];
head[start] = x;
++indeg_[end];
}
int Topsort(){
int i,flag = 0,cnt = 0,top;
queue<int> Q;
for(i = 1;i <= n;++i){
indeg[i] = indeg_[i];
if(!indeg[i]){
Q.push(i);
result[++cnt] = i + 'A' - 1;
if(flag)return 0;
flag = 1;
}
}
while(!Q.empty()){
top = Q.front();
Q.pop();
flag = 0;
for(i = head[top];i;i = side[i].next){
--indeg[side[i].e];
if(!indeg[side[i].e]){
Q.push(side[i].e);
result[++cnt] = (char)(side[i].e + 'A' - 1);
if(flag)return 0;
flag = 1;
}
}
}
if(cnt < n)return 0;
return 1;
}
int vis[Maxn];
int check(int x){
int i;
vis[x] = 1;
for(i = head[x];i;i = side[i].next){
if(vis[side[i].e])return 0;
if(!check(side[i].e))return 0;
}
vis[x] = 0;
return 1;
}
int main(){
int i,j;
char ch1,ch2,temp;
scanf("%d%d",&n,&m);
for(i = 1;i <= m;++i){
memset(vis,0,sizeof(vis));
getchar();
scanf("%c",&ch1);
getchar();
scanf("%c",&ch2);
add(c2i(ch1),c2i(ch2),i);
if(!check(c2i(ch1))){
printf("Inconsistency found after %d relations.",i);
return 0;
}
if(Topsort()){
printf("Sorted sequence determined after %d relations: %s",i,result+1);
return 0;
}
}
printf("Sorted sequence cannot be determined.");
return 0;
}
只拿了20分……
第一个数据点:
4 6
C<D
C<B
B<A
C<D
D<A
A<A
输出:
Inconsistency found after 6 relations.
我在自己电脑上运行是正确的,有大佬知道为什么吗