拓扑排序判断环 P1347 排序题解

题目

P1347 排序 - 洛谷
 

题目说的意思是，给定m组关系，当你判断是否可以确定这n个元素的大小关系，如果可以的话，就直接输出，不行分为两种，一种是不能确定关系，另一种是有矛盾。

思路

看我刚说的三种情况，我们如果以每一个元素看作一个节点，每条关系看作一个边，那么有解的情况对应的就是有稳定的顺序，无法确定就是没办法输出结果，矛盾的情况就是有环；

于是我们可以考虑拓扑排序，随后判断有没有环。如果最后所有关系都被输入，既没有满足有稳定顺序，也不满足矛盾，就证明条件不够。

1.建图

题目说了全是小于，于是直接add(u,v)就好，没有什么需要注意的（

其实就是建图的时候注意记录入度就好了。如果你连什么是拓扑排序都不知道的话

图论——拓扑排序-CSDN博客

2.拓扑的过程

顶点：A、B、C、D、E

边：A -> B，A -> C，B -> D，C -> D，D -> E

首先，找到入度为 0 的顶点，A 。输出 A ，然后删除 A 及其相关的边，此时 B 和 C 的入度变为0（代码里就应该把B和C入队） 。接着，选择 B 输出，删除 B 及其相关的边，此时 D 的入度变为 0 。然后，输出 C ，再输出 D ，最后输出 E ，完成拓扑排序。

3.判断环

在一次拓扑完了过后，如果说队列里同时有两个点，及比如上边的B，C都是入度为0，就代表我们有两种选择，也就是无论如何也不可能是唯一的序列。

我们也需要存一下拓扑排序的排序结果。这样才可以判断环。如果没有的话，拓扑排序会输出所有的节点，也就是拓扑的长度等于节点数。如果有环，那环中所有节点都不为0，根本无法入队，所以拓扑排序根本开始不了，长度小于节点数

所以如果排序后的数量小于节点总数，就是有环，可以判断关系矛盾

所以，我们可以得出一下代码：

while (!q.empty()) {if (q.size() > 1) {ue = false;}int x = q.front();q.pop();res[res_size++] = x;for (int i = head[x]; i; i = ne[i]) {int y = to[i];trd[y]--;if (trd[y] == 0) {q.push(y);}}
}

AC代码

#include<bits/stdc++.h>
using namespace std;int to[1000], ne[1000], head[30];
int rd[30];
int idx, n, m;
bool mp[30][30];void add(int x, int y) {if (!mp[x][y]) {mp[x][y] = true;to[++idx] = y;ne[idx] = head[x];head[x] = idx;rd[y]++;}
}int main() {cin >> n >> m;memset(head, 0, sizeof(head));memset(rd, 0, sizeof(rd));memset(mp, 0, sizeof(mp));idx = 0;for (int step = 1; step <= m; step++) {char a, op, b;cin >> a >> op >> b;int u = a - 'A';int v = b - 'A';add(u, v);int trd[30];memcpy(trd, rd, sizeof(int) * n);queue<int> q;for (int i = 0; i < n; i++) {if (trd[i] == 0) {q.push(i);}}int res[30];int res_size = 0;bool ue = true;while (!q.empty()) {if (q.size() > 1) {ue = false;}int x = q.front();q.pop();res[res_size++] = x;for (int i = head[x]; i; i = ne[i]) {int y = to[i];trd[y]--;if (trd[y] == 0) {q.push(y);}}}if (res_size != n) {cout << "Inconsistency found after " << step << " relations." << endl;return 0;}if (ue) {cout << "Sorted sequence determined after " << step << " relations: ";for (int i = 0; i < res_size; i++) {cout << (char)('A' + res[i]);}cout << "." << endl;return 0;}}cout << "Sorted sequence cannot be determined." << endl;return 0;
}