代码:
#include<bits/stdc++.h>
#define g_c getchar()
using namespace std;
const int N = 610;
int n, m;
struct E {
int from, to, nxt;
} edge[N];
int sz, head[N], in_deg[N], in_deg_[N];
int c_t, topo[N], cnt;
set<int> st;
inline void add(int u, int v) {
edge[++sz] = {u, v, head[u]}, head[u] = sz, in_deg[v]++;
}
inline int toposort() {
queue<int> q; c_t = cnt = 0;
memset(topo, 0, sizeof topo);
for (int i = 1; i <= n; i++) in_deg_[i] = in_deg[i];
for (int i = 1; i <= n; i++) if (!in_deg_[i]) q.push(i), cnt++;
if (cnt > 1) return 0;
bool flag = true;
for (int u, v, tmp = 0; q.size(); tmp = 0) {
topo[++c_t] = u = q.front(); q.pop();
for (int i = head[u]; i; i = edge[i].nxt)
if (!--in_deg_[v = edge[i].to]) tmp++, cnt++, q.push(v);
if (tmp > 1) flag = false;
}
if (cnt < st.size()) return -1;
if (!flag) return 0;
return (c_t == n);
}
signed main() {
scanf("%d%d", &n, &m);
for (int T = 1, u, v, p; T <= m; T++) {
g_c, u = g_c - 64, g_c, v = g_c - 64, add(u, v);
if(u == v) return printf("Inconsistency found after %d relations.", T), 0;
st.insert(u), st.insert(v);
p = toposort();
if (!~p) return printf("Inconsistency found after %d relations.", T), 0;
if (p) {
printf("Sorted sequence determined after %d relations: ", T);
for (int i = 1; i <= n; i++) printf("%c", topo[i] + 64);
putchar('.'); return 0;
}
}
puts("Sorted sequence cannot be determined.");
return 0;
}
其中,2#为:
input:
4 6
C<D
C<B
B<A
C<D
D<A
A<A
output:
Inconsistency found after 6 relations.
本地上测试答案没问题,可在评测机上输出首字母显示'S',请问是出了什么问题?