【算法竞赛 - 数据结构】加权并查集的理解（以POJ1703为例）

Livinfly

发布于 2022-10-26 16:24:31

2430

发布于 2022-10-26 16:24:31

文章被收录于专栏：Livinfly

题目跳转

POJ1703

题目大意

有两组人，有两样操作：

A x y，输出x和y的关系。没关系，相同，对立。
D x y，表示x和y关系对立。

思路

~~重新学~~加权并查集

通过加权代表的相对距离，表示集合内的各人员的类别。

是否在一个集合内表示是不是有关系，具体的关系，是另外维护的。

本题的类别只有2类，所以采用2进制下的加减法——异或实现，更新的原理，如下图。

外部更新，用原来的“父亲”来更新；内部更新，通过递归实现。

此为笔者刚预习的浅见，若有错误，请邮箱或QQ联系，指错。

CODE

#pragma GCC optimize(2)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n, m;
int fa[N], d[N];

int get_fa(int x)
{
  if (fa[x] == x)
    return x;
  int root = get_fa(fa[x]);
  d[x] ^= d[fa[x]];
  return fa[x] = root;
}

int main()
{
  // freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  int T;
  scanf("%d", &T);
  while (T--)
  {
    memset(d, 0, sizeof d);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
      fa[i] = i;
    while (m--)
    {
      char op[2];
      int a, b;
      scanf(" %s%d%d", op, &a, &b);
      int ta = get_fa(a), tb = get_fa(b);
      if (*op == 'D')
      {
        if (ta != tb)
        {
          fa[tb] = ta;
          d[tb] = d[ta] ^ d[a] ^ d[b] ^ 1;
        }
      }
      else
      {
        if (ta != tb)
          puts("Not sure yet.");
        else if (d[a] == d[b])
          puts("In the same gang.");
        else
          puts("In different gangs.");
      }
    }
  }
  return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年08月12日，如有侵权请联系 cloudcommunity@tencent.com 删除

ode