20pts,2#本地测试与评测机测试结果不同
  • 板块P1347 排序
  • 楼主__int__
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/8/19 11:15
  • 上次更新2024/8/19 13:41:35
查看原帖
20pts,2#本地测试与评测机测试结果不同
470465
__int__楼主2024/8/19 11:15

代码:

#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',请问是出了什么问题?

2024/8/19 11:15
加载中...