很奇怪,WA2
  • 板块P1347 排序
  • 楼主senak
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/2 19:57
  • 上次更新2024/7/2 20:14:10
查看原帖
很奇怪,WA2
1201076
senak楼主2024/7/2 19:57
#include<cstring>
#include<algorithm>
#include<set>
#include<iostream>
#include<vector>
#include<cmath>
#include<queue>
#define int long long
using namespace std;
const int N = 1007;
vector<int>edge[N];
int ind[N];
int IND[N];
int vis[N];
int n, m;
set<int>ans;
int status;
int SENAK = 0;
int CNT = 0;
void topsort(int CNT) {
	for (int i = 1; i <= n; i++) {
		ind[i] = IND[i];
	}
	ans.clear();
	queue<int>q;
	for (int i = 1; i <= n; i++) {
		if (ind[i] == 0 && vis[i]) {
			q.push(i);
		}
	}
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		ans.insert(cur);
		for (auto nxt : edge[cur]) {
			ind[nxt]--;
			if (ind[nxt] == 0) {
				q.push(nxt);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (ind[i] != 0) {
			status = -1;//没有
			break;
		}
	}
	if (ans.size() == n) {
		status = 1;//好的
	}
}
void solve() {
	cin >> n >> m;
	int FF = 0;
	for (int i = 1; i <= m; i++) {
		char a, b, c; cin >> a >> b >> c;
		if (!FF) {
			if (b == '<') {
				edge[c - 'A' + 1].push_back(a - 'A' + 1);
				IND[a - 'A' + 1]++;
				vis[a - 'A' + 1] = 1;
				vis[c - 'A' + 1] = 1;
			}
			else {
				edge[a - 'A' + 1].push_back(c - 'A' + 1);
				IND[c - 'A' + 1]++;
				vis[a - 'A' + 1] = 1;
				vis[c - 'A' + 1] = 1;
			}
			topsort(i);
			if (status == -1) {
				CNT = i;
				SENAK = 1;
				FF = 1;
			}
			if (status == 1) {
				SENAK = 2;
				CNT = i;
				FF = 1;
			}
		}
	}
	if (SENAK == 1) {
		printf("Inconsistency found after %d relations.\n", CNT);
	}
	else if (SENAK == 2) {
		printf("Sorted sequence determined after %d relations: ", CNT);
		for (auto c : ans) {
			cout << (char)(c - 1 + 'A');
		}cout << "." << endl;
	}
	else {
		cout << "Sorted sequence cannot be determined." << endl;
	}
}
signed main() {
	solve();
	return 0;
}

输入

4 6
C<D
C<B
B<A
C<D
D<A
A<A

输出

Inconsistency found after 6 relations.

我的输出

Sorted sequence determined after 3 relations: ABCD.

这个样例应该是前面三个就可以确定关系了吧?然后题目自己说的确定关系后就不用管了,那么为啥错了呢?

2024/7/2 19:57
加载中...