数据结构---并查集拓展

前言

并查集链接
关于并查集的更多知识点

拓展域并查集

扩展域并查集的本质就是用空间换逻辑清晰度。它将“节点与节点之间复杂的相对关系”，转化为“不同状态节点之间的绝对连通关系”。
食物链

点击查看代码

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
// #define int long long
const int N = 5e4 + 5;
// 扩展域并查集  n+1~2n为捕食关系，2n+1~3n为天敌关系
int fa[N * 3];
int n, k;
int find(int x)
{
  return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void unit(int x, int y)
{
  fa[find(x)] = find(y);
}

void solve()
{
  for (int i = 0; i < N * 3; i++)
  {
    fa[i] = i;
  }

  cin >> n >> k;
  int cnt = 0;
  for (int i = 0; i < k; i++)
  {
    int op, x, y;
    cin >> op >> x >> y;
    if (x > n || y > n)
    {
      cnt++;
      // cout<<"i="<<i<<endl;
      continue;
    }
    if (op == 1)
    {
      if (find(x) == find(y + n) || find(x) == find(y + 2 * n))
      {
        cnt++;
        // cout<<"i="<<i<<endl;
        continue;
      }
      unit(x, y);
      unit(x + n, y + n);
      unit(x + 2 * n, y + 2 * n);
    }
    else // x吃y
    {
      if (find(x) == find(y) || find(x) == find(y + n))
      {
        cnt++;
        // cout<<"i="<<i<<endl;
        continue;
      }
      unit(x + n, y);
      unit(x + 2 * n, y + n);
      unit(x, y + 2 * n);
    }
  }
  cout << cnt << endl;
}

signed main()
{
  IOS;
  int T;
  T = 1;
  // cin >> T;
  while (T--)
  {
    solve();
  }
  return 0;
}

团伙

点击查看代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
int fa[MAXN * 2];

int find(int x)
{
  if (x == fa[x])
    return x;
  return fa[x] = find(fa[x]);
}

void unite(int x, int y)
{
  int fx = find(x);
  int fy = find(y);
  if (fx != fy)
  {
    fa[fx] = fy;
  }
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  // 1~n 为本体域，n+1~2n 为敌人域
  for (int i = 1; i <= 2 * n; i++)
  {
    fa[i] = i;
  }
  for (int i = 0; i < m; i++)
  {
    char opt;
    int p, q;
    cin >> opt >> p >> q;

    if (opt == 'F')
    {
      // p 和 q 是朋友 -> 直接合并本体
      unite(p, q);
      // 朋友的敌人不一定是敌人的朋友所以unite(p + n, q + n);不加
    }
    else if (opt == 'E')
    {
      // p 和 q 是敌人
      // 敌人的敌人是朋友
      unite(p + n, q);
      unite(q + n, p);
    }
  }

  int cnt = 0;

  for (int i = 1; i <= n; i++)
  {
    if(find(i) == i)
    {
      cnt++;
    }
  }

  cout << cnt << endl;

  return 0;
}

带权并查集

带权并查集的精髓在于：我们根本不在乎点是什么，我们只维护点与点之间的“距离”或“关系”。
写带权并查集，脑子里画这三幅图：

1，节点含义：所有点都在一个坐标系里，d[x] 是 x 到原点的坐标。
2，路径压缩：x -> root 的距离 = x -> pa 的距离 + pa -> root 的距离（向量加法）。
3，集合合并：已知 x 和 y 的相对距离，倒推它们老大 rootX 和 rootY 的相对距离（向量减法）。

食物链
食物链问题的本质是：在一个周长为 3 的圆环上的向量运算。 所有的加减法逻辑与普通向量完全一致，只是最后多了一步取模，把无限长的数轴卷成了一个圈。

点击查看代码

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 50005; // 【修改1】范围由 1000 改为 50005
int fa[N], d[N];

int find(int x)
{
  if (fa[x] == x)
  {
    return x;
  }
  int root = find(fa[x]);       // 1. 先保存根节点
  d[x] = (d[x] + d[fa[x]]) % 3; // 2. 更新权值：当前到原父节点 + 原父节点到根
  fa[x] = root;                 // 3. 路径压缩
  return root;
}

// 计算 x 到 y 的相对关系 (d[x] - d[y])
int dist(int x, int y)
{
  return (d[x] - d[y] + 3) % 3;
}

void solve()
{
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; i++)
  {
    fa[i] = i;
    d[i] = 0;
  }
  int cnt = 0;
  for (int i = 0; i < k; i++)
  {
    int op, x, y;
    cin >> op >> x >> y;

    // 题目条件：如果 X 或 Y 比 N 大，是假话
    // 题目隐含条件：如果 op=2 且 X=Y，也是假话（自己吃自己）
    if (x > n || y > n || (op == 2 && x == y))
    {
      cnt++;
      continue;
    }

    int fx = find(x);
    int fy = find(y);

    if (op == 1) // 说法：X 和 Y 是同类
    {
      if (fx == fy)
      {
        // 如果在同一棵树，检查关系是否矛盾
        // 同类意味着 d[x] 和 d[y] 对 3 同余，即差值为 0
        if (dist(x, y) != 0)//x,y在同一颗树且不在同一层，则不是同类，是假话
          cnt++;
      }
      else
      {
        // 合并：让 x 的根指向 y 的根
        fa[fx] = fy;
        // 关系推导：(d[x] + d[fx]) % 3 == d[y] % 3
        // => d[fx] = d[y] - d[x]
        d[fx] = (d[y] - d[x] + 3) % 3;//x,y应在同一层，到根的距离应相等，d[fx]+d[x]=d[y],d[x]为到fx的距离
      }
    }
    else // 说法：X 吃 Y
    {
      if (fx == fy)
      {
        // X 吃 Y 意味着：(d[x] - d[y]) % 3 == 1
        if (dist(x, y) != 1) //x,y在同一颗树且x不在y的下一层，则不满足x吃y，是假话
          cnt++;
      }
      else
      {
        // 合并
        fa[fx] = fy;
        // 关系推导：X 吃 Y => (d[x] + d[fx] - d[y]) % 3 == 1
        // => d[fx] = d[y] - d[x] + 1
        d[fx] = (d[y] - d[x] + 1 + 3) % 3;//x应在y的下一层，到根的距离应多1，d[fx]+d[x]=d[y]+1
      }
    }
  }
  cout << cnt << "\n";
}

int main()
{
  IOS;
  solve();
  return 0;
}

可删除并查集

可回滚并查集