只需要在拓扑排序的时候维护一个flag,也就是说如果有一次入度为0的点超过1个,那结果就不唯一。
如果结果小于当前的字母数量,就是出现了环。如果结果唯一,并且数量等于n的话,我们就可以直接输出结果。
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int cnt, n, m, type, d[26], f[26];
bool st[26];
void topsort(int i, vector<int> graph[]) {
queue<int> q;
memcpy(d, f, sizeof f);
for (int i = 0; i < n; ++i) {
if (d[i] == 0) q.push(i);
}
string ans;
bool unique = true;
while (!q.empty()) {
if (q.size() > 1) unique = false;
int cur = q.front();
ans += 'A' + cur;
q.pop();
for (int ne : graph[cur]) {
if (--d[ne] == 0) q.push(ne);
}
}
if (ans.size() < cnt) {
type = 2;
printf("Inconsistency found after %d relations.\n", i);
}
if (ans.size() == n && unique) {
type = 1;
printf("Sorted sequence determined after %d relations: %s.\n", i, ans.c_str());
}
}
int main() {
string s;
while (cin >> n >> m, n || m) {
memset(f, 0, sizeof f);
memset(st, 0, sizeof st);
type = 0;
cnt = 0;
vector<int> graph[26];
for (int i = 1; i <= m; ++i) {
cin >> s;
if (type) continue;
int a = s[0] - 'A', b = s[2] - 'A';
if (!st[a]) {
st[a] = true;
++cnt;
}
if (!st[b]) {
st[b] = true;
++cnt;
}
graph[a].push_back(b);
f[b]++;
topsort(i, graph);
}
if (!type) printf("Sorted sequence cannot be determined.\n");
}
return 0;
}
合理,我也是第一个想到拓扑排序,但是在判断是否合法的时候并没有用拓扑排序,还是用floyd来判断了
大佬