下载了#2的数据,本地跑过了,洛谷IDE也过了, 提交时就WA
input :
4 6
C<D
C<B
B<A
C<D
D<A
A<A
expected output:
Inconsistency found after 6 relations.
code:
#include<bits/stdc++.h>
using namespace std;
const int N = 1000;
int n, m, idx, h[N], deg[N];
bool appear[N];
struct node {
int to, ne;
} e[N];
void add(int u, int v) {
e[++ idx].to = v;
e[idx].ne = h[u];
h[u] = idx;
deg[v] ++;
appear[u] = 1;
appear[v] = 1;
}
int cpy[N];
int find() {
int res = 0;
for(int i = 1; i <= n; i ++)
if(!cpy[i]) {
if(res) return -1;
res = i;
}
return res;
}
string order;
int topo() {
order.clear();
for(int i = 1; i <= n; i ++)
cpy[i] = deg[i];
int st = find();
if(!st) return 0;
if(!~st) return -1;
queue<int> q;
q.push(st);
while(!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u - 1 + 'A');
bool flag = 0;
for(int i = h[u]; ~i; i = e[i].ne) {
int v = e[i].to;
if(-- cpy[v] == 0) {
if(flag) return -1; //无法确定顺序
flag = 1;
q.push(v);
}
}
}
int n_of_appear = 0;
for(int i = 1; i <= n; i ++)
if(appear[i]) n_of_appear ++;
if(order.size() < n_of_appear) return 0;
else return 1;
}
int main() {
int u, v;
char s1, s2;
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
bool finished = 0;
for(int i = 1; i <= m; i ++) {
getchar();
scanf("%c<%c", &s1, &s2);
if(finished) continue;
u = s1 - 'A' + 1; v = s2 - 'A' + 1;
if(u == v) {
finished = 1;
printf("Inconsistency found after %d relations.\n", i);
}
add(u, v);
int res = topo();
if(res == 1) {
printf("Sorted sequence determined after %d relations: %s.\n", i, order.c_str());
finished = 1;
}
else if(res == 0) {
printf("Inconsistency found after %d relations.\n", i);
finished = 1;
}
}
if(!finished)
printf("Sorted sequence cannot be determined.\n");
}