给定点之间的关系，让你判断序列是否唯一或者非法。
注意的是 点之间相等的话总是可以根据另一种关系排序，所以如果某些点相等的话就不用考虑他们之间的关系了（他们之间的排序是唯一且固定的），而且他们在总排序上是连续的。 所以相等的一些点可以看成一个连通分量，采取“缩点”的思想，他们可以由其中的一个点代表。 所以问题就是，怎么判断有环（也是非法的一种），怎么判断不唯一，怎么判断“绝对非法”（就是A=B A>B或者A>A这种，可以归结为连通分量内不能再有大小关系）。 需要注意的是，这里判环是有向图，所以可以用拓扑排序，可以判断各种环（有环连通图、有环不连通图），入队列的都是每个连通分量的代表，判断出队的个数与连通分量的个数即可。至于怎样判断不唯一，当某次队列中存在的点个数大于1时，实际上这时候已经造成排序不唯一了，因为这几个点的次序无法确定！而且这个方法也顺便把不连通给判断了（想象一下，若不连通且没环，则一开始队列就会入至少两个点吧）。 当然，有一种情况：A=B B>C A>C 这种情况是正确的（若A，B合为A，A的边表里有两个C，在A出队列时会遍历它的每一条边（两个C），相当于替B遍历了一个，实际上相当于这时候B也出去了，所以C的入度会降为0，没有问题）。#include#include #include #include #include using namespace std;const int MAXN = 1e4 + 10;int N, M;int pre[MAXN];struct Edge{ int from, to;};vector ve;vector v[MAXN];int indegree[MAXN];int flag;int f(int x){ int f0 = x, f1 = x; for (; pre[f0] >= 0;) f0 = pre[f0]; for (; pre[f1] >= 0;) { int t = f1; f1 = pre[f1]; pre[t] = f0; } return f0;}void u(int n1, int n2){ int f1 = f(n1); int f2 = f(n2); if (f1 != f2) { if (pre[f1] <= pre[f2]) { pre[f1] += pre[f2]; pre[f2] = f1; } else { pre[f2] += pre[f1]; pre[f1] = f2; } }}void topological(){ int points = 0; int q_times = 0; queue q; for (int i = 0; i < N; i++) { if (pre[i] < 0) { points++; if (!indegree[i]) q.push(i); } } if (q.empty()) // 全图就是一个大环，这里只是提前判断一下 { flag = 1; return; } for (; !q.empty();) { if (q.size() > 1) flag = 2; // 若不连通这里一定会揪出来 int t = q.front(); q.pop(); q_times++; for (int i = 0; i < v[t].size(); i++) { indegree[v[t][i]]--; if (!indegree[v[t][i]]) q.push(v[t][i]); } } if (points != q_times) flag = 1;}int main(){ int a, b; char c; for (; ~scanf("%d%d", &N, &M);) { memset(pre, -1, sizeof pre); ve.clear(); flag = 0; for (int i = 0; i < N; i++) { v[i].clear(); indegree[i] = 0; } for (int i = 0; i < M; i++) { scanf("%d %c %d", &a, &c, &b); if (c == '=') u(a, b); else if (c == '>') ve.push_back({ a,b }); else if (c == '<') ve.push_back({ b,a }); } for (int i = 0; i < ve.size(); i++) { int n1 = f(ve[i].from); int n2 = f(ve[i].to); if (n1 == n2) { printf("CONFLICT\n"); flag = 1; break; } v[n1].push_back(n2); indegree[n2]++; } if (flag) continue; topological(); if (flag == 1) printf("CONFLICT\n"); else if (flag == 2) printf("UNCERTAIN\n"); else printf("OK\n"); } return 0;}