试了一下,开O2就过不了,但是不开就AC了
#include<bits/stdc++.h>
using namespace std;
vector<int>mapp[650];
int n,m,flag=-1,k=0;
int in[650];
int in1[650];
int bo[650];
bool cir;
int kkk=0;
void sort_topo(int ppp){
vector<char>map1;
queue<int>q;
int cnt;
for(int i=1;i<=n;i++){
if(in1[i]==0&&bo[i]){
q.push(i);
cnt++;
if(cnt>1)flag=2;
}
//TODO
}
while(!q.empty()){
int topo1=q.front();
int sizen=mapp[topo1].size();
map1.push_back(topo1-1+'A');
// printf("%d ",topo1);
cnt=0;
q.pop();
for(int i=0;i<sizen;i++){
in1[mapp[topo1][i]]--;
if(in1[mapp[topo1][i]]==0){
q.push(mapp[topo1][i]);
cnt++;
}
//TODO
}
if(cnt>1)flag=2;
//TODO
}
// printf("size:%d\n",map1.size());
if(map1.size()<kkk){
flag=0;
return ;
}
if(map1.size()==n&&flag!=2){
flag=1;
printf("Sorted sequence determined after %d relations: ",ppp);
int sz=map1.size();
for(int i=0;i<map1.size();i++){
cout<<map1[i];
}
printf(".");
return ;
}
return ;
}
int main(){
// printf("%d %d\n",'A','B');
scanf("%d%d",&n,&m);
memset(bo,0,sizeof(bo));
for(int i=1;i<=m;i++){
string a;
cin>>a;
int x=a[0]+1-'A';
if(!bo[x]){
bo[x]=1;
kkk++;
}
int y=a[2]+1-'A';
if(!bo[y]){
bo[y]=1;
kkk++;
}
// printf("%d %d\n",x,y);
mapp[x].push_back(y);
in[y]++;
flag=-1;
for(int j=1;j<=26;j++)in1[j]=in[j];
sort_topo(i);
if(flag==1){
return 0;
}
if(flag==0){
printf("Inconsistency found after %d relations.",i);
return 0;
}
}
printf("Sorted sequence cannot be determined.");
// sort_topo();
return 0;
}
第一个和第九个过不了
26 26
A<B
B<C
C<D
D<E
E<F
F<G
G<H
H<I
I<J
J<K
K<L
L<M
M<N
N<O
O<P
P<Q
Q<R
R<S
S<T
T<U
U<V
V<W
W<X
X<Y
Y<Z
Z<A
第一个输入
Sorted sequence determined after 25 relations: ABCDEFGHIJKLMNOPQRSTUVWXYZ.
第一个输出