#|HDU1811 Rank of Tetris——拓扑排序（BFS+并查集）刷题|搜索技术|拓扑排序

【#|HDU1811 Rank of Tetris——拓扑排序（BFS+并查集）】点这里
题意： n个人个m个约束条件，每行约束条件都有“<>=”符号，“=”表示两人同级，两个人之间编号大的在前。按照已知条件如果排名唯一，则输出OK；排名不唯一则输出UNCERTAIN；约束条件之间矛盾则输出CONFLICT。
题解：

缩点（并查集）。不要想的太复杂（我就是一直在考虑“=”怎么处理，一直没敢下手）其实所有=联系的点，合并成一个点处理即可，他们内部的排名肯定是能够确认的，题目不要求输出排名，那就不用在意，看成一个点处理就行。这步处理，则是采用并查集的方式。
CONFLICT。什么样情况下会矛盾，其实应该说条件矛盾会造成什么后果。一种情况是同时出现a = b和a > b，这个很容易判断，一开始读入的时候，就可以将所有“=”的两个点合并，之后再遍历每一条边，检查是否有冲突。第二种情况是出现a > b和a < b的环，造成的后果是拓扑排序的BFS中，出现一些点的入度不为零，无法入队，这种情况只要跑完一遍BFS检查是否还要入度不为零的点即可。
UNCERTAIN。想一下什么条件可能造成最后排名不唯一，可一句样例1 > 0, 1 > 2, 2 < 1，如果去掉重边，观察0、1、2三个点的入度分别为0、1、1。也就是说再遍历点1的边时，0和2的入度会同时减为0，并且入队。即如果在BFS排序过程中，队列中出现了两个及以上的元素，说明最终排名可能不唯一。

过程中犯的错：

sum可能为负。虽然进行了缩点，，但实际上的点数没有改变。（sum的初始值为n，程序中每出现一次“=”，sum就会减一；每当一个点入队，sum就会减一），进行过缩点操作之后，我的程序中认可的点可能只有x个，但是出现的点可能一共会有n个，n如果＞x，sum会出现负数。所以检查是否所有（认可的）点都入队，应判断最后的sum>0?而不是判断sum==0?
BFS函数必须完整执行。一开始我一旦找到队列中包含两个及以上的元素，说明最后排名可能不唯一的时候，我写了一个return。实际上如果这个函数不执行完的话，还会影响sum的结果，而sum的结果先影响了是否输出UNCERTAIN。因此这里不能return。

#include using namespace std; const int N = 1e4 + 10; int n, m, sum; int deg[N], s[N]; bool flag, sign; vector v[N]; struct edge{ int x, y; char c; }e[2 * N]; int find(int x){ return s[x] == x? x: s[x] = find(s[x]); } void un(int a, int b){ int sa = find(a), sb = find(b); if(sa != sb) s[sa] = sb; } void check(){ for(int i = 0; i < m; i++){ if(e[i].c == '=') continue; int a = find(e[i].x), b = find(e[i].y); if(a == b){ flag = false; return; } if(e[i].c == '<'){ deg[a]++; v[b].push_back(a); }else{ deg[b]++; v[a].push_back(b); } } } void BFS(){ queue q; for(int i = 0; i < n; i++){ int a = find(i); if(!deg[a] && s[a] == i) q.push(a); } while(!q.empty()){ int a = q.front(); q.pop(); sum--; if(!q.empty()) sign = false; //不能return for(int i = 0; i < v[a].size(); i++){ int b = v[a][i]; deg[b]--; if(!deg[b]) q.push(b); } } } int main(){ while(~scanf("%d%d", &n, &m)){ sum = n; flag = sign = true; for(int i = 0; i < n; i++) deg[i] = 0, s[i] = i, v[i].clear(); //init(); for(int i = 0; i < m; i++){ scanf("%d %c %d", &e[i].x, &e[i].c, &e[i].y); if(e[i].c == '=') un(e[i].x, e[i].y), sum--; } check(); BFS(); if(sum > 0 || !flag)printf("CONFLICT\n"); //不能 sum != 0 else if(!sign)printf("UNCERTAIN\n"); elseprintf("OK\n"); } return 0; }