hdu 3234 Exclusive-OR （并查集）

2023-10-07 18:20

文章标签 查集 hdu 3234 exclusive

本文主要是介绍hdu 3234 Exclusive-OR （并查集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem - 3234

　　题意不难理解，就是给出一些断言，以及一些查询，回答查询或者在找到断言矛盾以后沉默不做任何事。

　　这题其实就是一个并查集的距离存储问题，只要记录并查集元素的相对值以及绝对值就可以了。

代码如下：

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <stack>
  6 #include <set>
  7 
  8 using namespace std;
  9 
 10 const int N = 22222;
 11 struct MFS {
 12     int fa[N], rel[N], val[N];
 13     void init() { for (int i = 0; i < N; i++) fa[i] = i, rel[i] = 0, val[i] = -1;}
 14     int find(int x) {
 15         if (fa[x] != x) {
 16             int fx = find(fa[x]);
 17             rel[x] ^= rel[fa[x]];
 18             fa[x] = fx;
 19             val[x] = val[fx] ^ rel[x];
 20             return fx;
 21         } else return x;
 22     }
 23     bool merge(int x, int y, int d) {
 24         int fx = find(x), fy = find(y);
 25         if (fx == fy) return d == (rel[x] ^ rel[y]);
 26         int dx = rel[x] ^ rel[fx], dy = rel[y] ^ rel[fy];
 27         if (~val[fx] && ~val[fy]) return d == (dx ^ dy ^ val[fx] ^ val[fy]);
 28         d ^= dx ^ dy;
 29         if (~val[fx]) rel[fy] ^= d, fa[fy] = fx;
 30         else rel[fx] ^= d, fa[fx] = fy;
 31         return true;
 32     }
 33     bool confirm(int x, int d) {
 34         int fx = find(x);
 35         if (~val[fx]) return (rel[x] ^ val[fx]) == d;
 36         val[fx] = rel[x] ^ d;
 37         return true;
 38     }
 39     int query(int x) {
 40         int fx = find(x);
 41         if (~val[x]) return val[x];
 42         return -1;
 43     }
 44 } mfs;
 45 
 46 set<int> nsid;
 47 int ns[N];
 48 
 49 int main() {
 50 //    freopen("in", "r", stdin);
 51     char buf[222];
 52     int n, m, val[111], cnt, cas = 1;
 53     while (~scanf("%d%d", &n, &m) && (n || m)) {
 54         mfs.init();
 55         bool conf = false;
 56         char *ptr;
 57         cnt = 0;
 58         printf("Case %d:\n", cas++);
 59         for (int q = 1; q <= m; q++) {
 60              scanf("%s", buf);
 61             gets(buf + 1);
 62             val[0] = 0;
 63             ptr = strtok(buf + 1, " ");
 64             while (ptr) {
 65                 val[0]++;
 66                 sscanf(ptr, "%d", &val[val[0]]);
 67                 ptr = strtok(NULL, " ");
 68             }
 69             if (conf) continue;
 70             if (buf[0] == 'I') {
 71                 cnt++;
 72                 if (val[0] == 3) conf = !mfs.merge(val[1], val[2], val[3]);
 73                 else conf = !mfs.confirm(val[1], val[2]);
 74                 if (conf) printf("The first %d facts are conflicting.\n", cnt);
 75             } else {
 76                 int ans = 0, tmp, fa;
 77                 nsid.clear();
 78                 for (int i = 2; i <= val[0]; i++) {
 79                     tmp = mfs.query(val[i]);
 80                     fa = mfs.find(val[i]);
 81 //                    cout << tmp << ' ';
 82                     if (tmp < 0) {
 83                         if (nsid.find(fa) != nsid.end()) {
 84                             ans ^= ns[fa] ^ mfs.rel[val[i]];
 85                             nsid.erase(fa);
 86                         } else {
 87                             nsid.insert(fa);
 88                             ns[mfs.fa[val[i]]] = mfs.rel[val[i]];
 89                         }
 90                     } else ans ^= tmp;
 91                 }
 92 //                cout << endl;
 93                 if (!nsid.empty()) puts("I don't know.");
 94                 else printf("%d\n", ans);
 95             }
 96         }
 97         puts("");
 98     }
 99     return 0;
100 }