【HDOJ】1811 Rank of Tetris

并查集+拓扑排序。使用并查集解决a = b的情况。
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <queue>
  5 using namespace std;
  6 
  7 #define MAXN 10005
  8 
  9 typedef struct ArcNode {
 10     int adjvex;
 11     ArcNode *next;
 12 } ArcNode;
 13 
 14 typedef struct VNode {
 15     int count;
 16     ArcNode *first;
 17 } VNode;
 18 
 19 VNode nodes[MAXN];
 20 int pre[MAXN], n;
 21 int srca[MAXN<<1],srcb[MAXN<<1];
 22 char op[MAXN<<1];
 23 bool flag;
 24 
 25 int find(int x) {
 26     int r = x;
 27     while (r != pre[r])
 28         r = pre[r];
 29     return r;
 30 }
 31 
 32 void merge(int a, int b) {
 33     int x = find(a);
 34     int y = find(b);
 35     pre[x] = y;
 36 }
 37 
 38 void Insert(int x, int y) {
 39     ArcNode *p = new ArcNode;
 40     nodes[y].count++;
 41     p->adjvex = y;
 42     p->next = nodes[x].first;
 43     nodes[x].first = p;
 44 }
 45 
 46 int main() {
 47     int m;
 48     int i, j, x, y;
 49 
 50     while (scanf("%d %d",&n,&m) != EOF) {
 51         for (i=0; i<n; ++i) {
 52             nodes[i].count = 0;
 53             nodes[i].first = NULL;
 54             pre[i] = i;
 55         }
 56         for (i=0; i<m; ++i) {
 57             scanf("%d %c %d", &srca[i], &op[i], &srcb[i]);
 58             if (op[i] == '=')
 59                 merge(srca[i], srcb[i]);
 60         }
 61         flag = false;
 62         for (i=0; i<m; ++i) {
 63             if (op[i] == '=')
 64                 continue;
 65             x = find(srca[i]);
 66             y = find(srcb[i]);
 67             if (x == y) {
 68                 flag = true;
 69                 break;
 70             }
 71             if (op[i] == '>')
 72                 Insert(x, y);
 73             else
 74                 Insert(y, x);
 75         }
 76         if (flag) {
 77             printf("CONFLICT
");
 78             continue;
 79         }
 80         queue<int> que;
 81         int index;
 82         ArcNode *p;
 83         m = 0;
 84         for (i=0; i<n; ++i) {
 85             if (i==find(i)) {
 86                 ++m;
 87                 if (nodes[i].count==0)
 88                     que.push(i);
 89             }
 90         }
 91         while (!que.empty()) {
 92             if (que.size() > 1)
 93                 flag = true;
 94             index = que.front();
 95             que.pop();
 96             p = nodes[index].first;
 97             --m;
 98             while (p != NULL) {
 99                 j = p->adjvex;
100                 --nodes[j].count;
101                 if (nodes[j].count == 0)
102                     que.push(j);
103                 p = p->next;
104             }
105         }
106         if (m)
107             printf("CONFLICT
");
108         else if (flag)
109             printf("UNCERTAIN
");
110         else
111             printf("OK
");
112     }
113 
114     return 0;
115 }