排序

链接

本题考查的就是拓扑排序,由于本题的数据量很少,我们可以直接用邻接矩阵来查重

这题要求输出唯一解,也就是说多解还需要继续输入

我们可以使用bfs,设一个队列q

如果在任何时刻q.size()>1,就意味着存在多解

又或者输出结果(也就是字符串长度)小于n,就意味着出现了环(入度不存在0的情况)

代码如下:

#include<iostream>
#include<vector>
#include<queue>
#include<string>
using namespace std;
int n, m;
vector<vector<bool>>edge(26, vector<bool>(26, 0));
vector<vector<int>>g(26);
vector<int>inge(26,0);

int topo(vector<int>& ans) {
	vector<int>in = inge;
	bool run = 1;
	queue<int>q;
	for (int i = 0;i < n;i++) {
		if (!in[i]) q.push(i);
	}
	while (!q.empty()) {
		if (q.size() > 1) run = 0;
		int cur = q.front();
		q.pop();
		ans.push_back(cur);
		for (int x : g[cur]) {
			if (--in[x] == 0) q.push(x);
		}
	}
	if (ans.size() < n) return -1;
	if (run) return 1;
	return 0;
}

int main() {
	cin >> n >> m;
	for (int i = 0;i < m;i++) {
		char a, opt, b;
		cin >> a >> opt >> b;
		int x = a - 'A', y = b - 'A';
		if (!edge[x][y]) {
			edge[x][y] = 1;
			inge[y]++;
			g[x].push_back(y);
		}
		vector<int>ans;
		int res = topo(ans);
		if (res == -1) {
			cout << "Inconsistency found after " << i + 1 << " relations.";
			return 0;
		}
		else if (res==1) {
			cout << "Sorted sequence determined after " << i + 1 << " relations: ";
			for (int num : ans) {
				cout << (char)(num + 'A');
			}
			cout << ".";
			return 0;
		}
	}
	cout << "Sorted sequence cannot be determined.";
}

时间复杂度:O(m log n)