uva 12232 - Exclusive-OR(加權並查集)

uva 12232 - Exclusive-OR(加權並查集)

題目鏈接：uva 12232 - Exclusive-OR

題目大意：有n個數，一開始並不知道具體的值，現在進行Q次操作。

• I u k：au的值為k
• I u v k：au?av=k
• Q k q1q2…qk：求q1?q2…?qk
  對於Q操作不能確定的話輸出"I don't know."
  對於I操作矛盾的話則輸出是第幾條I操作出現矛盾的，並且停止後面所有的操作。

  解題思路：加權並查集，f[x]表示x節點父親節點，d[x]表示x節點與其父節點的亦或值，對於確定的節點值，可以將父親節點設為0，這樣的話在合並操作的時候就要注意，如果有一段0是父親節點的話，就要將令一個節點指向0節點（也就是說0節點是固定不能有父親節點的），一是在指向0節點的聯通集合是確定值的，在查詢是需要特判，二是進行第一種操作的時候方便處理。
  在查詢時，需要將所有的數分成各個聯通集合，如果存在聯通集合的個數為奇數，並且根節點不為0的話就是不能確定值的，否則取所有節點與父親節點的亦或值的亦或和即可。

  #include 
  #include 
  #include 
  
  using namespace std;
  const int maxn = 20005;
  const int maxm = 105;
  
  bool flag;
  int N, Q, f[maxn], d[maxn];
  
  int getfar (int x) {
  
      if (x == f[x])
          return x;
  
      int tmp = f[x];
      f[x] = getfar(f[x]);
      d[x] ^= d[tmp];
      return f[x];
  }
  
  void query () {
      int n, ret = 0, num[maxm], vis[maxm];
      memset(vis, 0, sizeof(vis));
  
      scanf("%d", &n);
      for (int i = 0; i < n; i++) {
          scanf("%d", &num[i]);
          num[i]++;
      }
  
      if (flag)
          return;
  
      for (int i = 0; i < n; i++) {
  
          int root = getfar(num[i]), cnt = 1;
          if (root == 0 || vis[i])
              continue;
  
          for (int j = i+1; j < n; j++) {
              if (getfar(num[j]) == root) {
                  cnt++;
                  vis[j] = 1;
              }
          }
  
          if (cnt&1) {
              printf("I don't know.\n");
              return ;
          }
      }
  
      for (int i = 0; i < n; i++)
          ret ^= d[num[i]];
      printf("%d\n", ret);
  }
  
  bool link () {
      char s[maxm];
      gets(s);
  
      int u, v, k;
      int type = sscanf(s, "%d%d%d", &u, &v, &k);
      u++;
  
      if (type == 2) {
          k = v;
          v = 0;
      } else
          v++;
  
      int p = getfar(u);
      int q = getfar(v);
  
      if (p == 0)
          swap(p, q);
  
      if (p != q) {
          f[p] = q;
          d[p] = d[u]^d[v]^k;
      } else
          return (d[u]^d[v]) != k;
      return false;
  }
  
  int main () {
      int cas = 1;
      while (~scanf("%d%d", &N, &Q) && N) {
  
          printf("Case %d:\n", cas++);
  
          flag = false;
          memset(d, 0, sizeof(d));
          for (int i = 0; i <= N; i++)
              f[i] = i;
  
          int ti = 0, u, v;
          char s[maxm];
          for (int i = 0; i < Q; i++) {
              scanf("%s", s);
  
              if (s[0] == 'I') {
                  ti++;
                  if (link()) {
                      flag = true;
                      printf("The first %d facts are conflicting.\n", ti);
                  }
              } else if (s[0] == 'Q')
                  query();
          }
          printf("\n");
      }
      return 0;
  }