HDU1811 Rank of Tetris {图论}【拓扑排序】（并查集）

题解

    给你$N$个点(编号从$0$到$N-1$)和$M$个关系，要你判断这个图的所有点的顺序是否可以全部确定。不过对于任意点的关系可能存在$A>B$或$A<B$或$A=B$三种情况，如果$A=B$的话，那么就比较他们的编号，编号大的点分数大。（如果$A=B$且$A$编号大于$B$编号,那么$A$分数大）。     输出结果有三种情况：缺少信息（即可拓扑排序），OK（能全排列），冲突（产生有向环）。     我们先按普通拓扑排序的过程来处理。     假设$A>B$或$B<A$，直接在$A$与$B$之间加一条有向边即可。     假设$A=B$呢？由于$A$与$B$的序号不同，所以我们最终还是可以在$A$与$B$间加一条有向边。     但是如果接下来又出现$C=A$呢？不仅$C$与$A$之间要加边，$C$与$B$之间也要加边的。甚至$C$与和$A$相等的所有点之间都要加边。     如果我们能做到上面的步骤，这个图就建立出来了。不过这个图就太复杂了。其实我们可以这么想，对于$A=B=C=\dots =E$这些（$Rating$相等但编号不等）都相等的边，他们之间肯定能分出确定的顺序的（因为它们编号肯定都不同）。     重点来了：我们把所有具有$=$关系的点都聚合成$1$点（合并为一个连通分量，且只用该分量的根节点代替分量中的所有点）。然后我们只处理$>$或$<$关系（添加两个分量根之间的有向边）。然后我们只需要判断这个缩减的图是否能全排序或拓扑排序或冲突即可。     如何判断一个有向图是否能全排序或拓扑排序或冲突呢？按照$topo$函数的处理过程来.如果从$Q$队列出去的$0$入度点等于所有连通分量的根数目，那么这个图肯定没冲突。     假设没冲突，且在队列$Q$中始终只有$1$个元素的话，说明该图可全排序。否则只能拓扑排序。     注意：题目中还有一个问题，我们必须保证所有具有相等关系的点不冲突。（即不会出现$A=B$，之后又来一个$A>B$关系）这点在代码中有体现。     转载至focus_bestf

#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <functional> #include <iostream> #include <map> #include <queue> #include <stack> #include <string> #include <vector> using namespace std; typedef long long ll; const int N = 1e5 + 10, NN = 1e3 + 10, INF = 0x3f3f3f3f; const ll MOD = 1e9 + 7; int num_edge, n, m, sum; int head[N], indegree[N], fa[N]; struct Edge { int next; int to; } edge[N]; struct Record { int temp1; int temp2; char id; } record[N]; int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } void baba(int x, int y) { int f1 = find(x); int f2 = find(y); fa[f1] = f2; } void add_edge(int from, int to) { num_edge++; edge[num_edge].next = head[from]; edge[num_edge].to = to; head[from] = num_edge; } void topo() { queue<int> q; for (int i = 0; i < n; i++) if (!indegree[i] && fa[i] == i) q.push(i); bool flag = false; while (!q.empty()) { if (q.size() > 1) flag = true; int u = q.front(); q.pop(); --sum; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; --indegree[v]; if (!indegree[v]) q.push(v); } } if (sum > 0) printf("CONFLICT\n"); else if (flag) printf("UNCERTAIN\n"); else printf("OK\n"); } void init() { num_edge = 0; sum = n; memset(head, -1, sizeof head); memset(indegree, 0, sizeof indegree); for (int i = 0; i <= n; i++) fa[i] = i; } int main() { while (~scanf("%d%d", &n, &m)) { init(); for (int i = 0; i < m; i++) { scanf("%d %c %d", &record[i].temp1, &record[i].id, &record[i].temp2); if (record[i].id == '=') baba(record[i].temp1, record[i].temp2); } bool flag = true; for (int i = 0; i < m; i++) { if (record[i].id == '=') { --sum; continue; } int u = find(record[i].temp1), v = find(record[i].temp2); if (u == v) { flag = false; break; } else if (record[i].id == '>') { add_edge(u, v); ++indegree[v]; } else if (record[i].id == '<') { add_edge(v, u); ++indegree[u]; } } if (!flag) printf("CONFLICT\n"); else topo(); } }