NO.79十六届蓝桥杯备战|数据结构-扩展域并查集-带权并查集|团伙|食物链|银河英雄传说(C++)

扩展域并查集

普通的并查集只能解决各元素之间仅存在⼀种相互关系，⽐如《亲戚》题⽬中：

• a 和b 是亲戚关系，b 和c 是亲戚关系，这时就可以查找出a 和c 也存在亲戚关系。
  但如果存在各元素之间存在多种相互关系，普通并查集就⽆法解决。⽐如下⾯的案例：
• a 和b 是敌⼈关系，b 和c 是敌⼈关系，但是a 和c 其实不是敌⼈关系，⽽是另⼀种朋友关系。
  此时，就不仅仅是简单的敌⼈关系，还是出现⼀种朋友关系。
  解决这类问题就需要对并查集进⾏扩展：将每个元素拆分成多个域，每个域代表⼀种状态或者关系。
  通过维护这些域之间的关系，来处理复杂的约束条件。
  敌⼈朋友问题中，我们会将x 分成两个域，朋友域x 以及敌⼈域y ：
• x 和y 是朋友，正常处理，把x 和y 合并成⼀个集合；
• x 和y 是敌⼈：那么x 和y 的敌⼈y+n 就是朋友，合并x 与y+n ；y 和x 的敌⼈x+n 就是朋友，合并y 与x+n 。
  这样就可以利⽤两个域，将所有的关系维护起来

P1892 [BalticOI 2003] 团伙 - 洛谷

扩展域并查集模板题：

• a 和b 如果是朋友，那就直接合并在⼀起；
• a 和b 如果是敌⼈，那就把a 和b + n 以及a + n 和b 合并在⼀起
  没有说朋友的敌人是敌人
  合并的时候要让朋友域作为父节点

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

const int N = 1010;

int n, m;
int fa[N * 2]; //扩展域并查集

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

//朋友域作为父节点
void un(int x, int y)
{
    fa[find(y)] = find(x);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    //初始化
    for (int i = 1; i <= n * 2; i++) fa[i] = i;
    while (m--)
    {
        char op; int x, y;
        cin >> op >> x >> y;
        if (op == 'F')
        {
            un(x, y);
        }
        else
        {
            un(x, y+n);
            un(y, x+n);
        }
    }

    int ret = 0;
    for (int i = 1; i <= n; i++)
    {
        if (fa[i] == i) ret++;
    }
    cout << ret << endl;
    
    return 0;
}

P2024 [NOI2001] 食物链 - 洛谷

针对x ，扩展三个域：同类域x，捕⻝域x+n，被捕⻝域x+n+n。
如果x和y是同类：

• x和y是同类
• x+n与y+n是同类
• x+n+n与y+n+n是同类
  如果x捕⻝y：
• x+n与y同类
• x与y+n+n同类
• x+n+n与y+n同类

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

const int N = 5e4 + 10;

int n, k;
int fa[N * 3]; //扩展域并查集

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

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;

    for (int i = 1; i <= n * 3; i++) fa[i] = i;

    int ret = 0;
    while (k--)
    {
        int op, x, y; cin >> op >> x >> y;
        if (x > n || y > n) ret++;
        else if (op == 1) //同类
        {
            if (find(x) == find(y+n) || find(x) == find(y+n+n)) ret++;
            else
            {
                un(x, y);
                un(x+n, y+n);
                un(x+n+n, y+n+n);
            }
        }
        else
        {
            if (find(x) == find(y) || find(x) == find(y+n)) ret++;
            else
            {
                un(x, y+n+n);
                un(y, x+n);
                un(x+n+n, y+n);
            }
        }
    }

    cout << ret << endl;
    
    return 0;
}

带权并查集

1. 带权并查集的概念
   带权并查集在普通并查集的基础上，为每个结点增加了⼀个权值。这个权值可以表⽰当前结点与⽗结点之间的关系、距离或其他信息（注意，由于我们有路径压缩操作，所以最终这个权值表⽰的是当前结点相对于根结点的信息）。有了这样⼀个权值，就可以推断出集合中各个元素之间的相互关系。
2. 带权并查集的实现
   我们以最简单的距离问题为例，实现⼀个能够查询任意两点之间距离的并查集。
   实现带权并查集的核⼼是在进⾏ Find 和 Union 操作时，不仅要维护集合的结构，还要维护结点的权值。
   注意：带权并查集的实现是多种多样的，基本上换⼀道题，实现的代码就要更改。因此⼀定要重点关注实现过程的思考⽅式，这才是通⽤的

初始化init ：

const int N = 1e5 + 10, INF = 0x3f3f3f3f;  
int n;  
int fa[N], d[N];  

void init()  
{  
	for(int i = 1; i <= n; i++)  
	{  
		fa[i] = i;  
		d[i] = 0; // 根据题⽬要求来初始化  
	}  
}

查询根节点操作 find ：

int find(int x)  
{  
	if(fa[x] == x) return x;  
	
	int t = find(fa[x]); // 这句代码⼀定要先执⾏，先让⽗结点挂在根节点的后⾯  
	d[x] += d[fa[x]]; // 注意，可能会根据权值的意义有所改变  
	
	return fa[x] = t;  
}

合并操作 union ：

// x 所在集合与 y 所在集合合并，x 与 y 之间的权值是 w  
void un(int x, int y, int w)  
{  
	int fx = find(x), fy = find(y);  
	
	if(fx != fy) // 不在同⼀个集合中  
	{  
		fa[fx] = fy;  
		d[fx] = d[y] + w - d[x]; // 注意，可能会根据权值的意义有所改变  
	}  
}

查询距离操作 query ：

// 查询 x 到 y 的距离  
int query(int x, int y)  
{  
	int fx = find(x), fy = find(y);  
	
	if(fx != fy) return INF; // 如果不在同⼀个集合中，说明距离未知  
	return d[y] - d[x];  
}

P2024 [NOI2001] 食物链 - 洛谷

把真话⾥⾯的相互关系，⽤"带权并查集"维护起来，权值表⽰当前节点相对于根节点的距离。那么对于集合中的任意两点x 和y ：

• 如果(d[y] - d[x]) % 3 == 0 ，表⽰两者是同类关系；
• 如果(d[y] - d[x]) % 3 == 1 ，表⽰两者是捕⻝关系；
• 如果(d[y] - d[x]) % 3 == 2 ，表⽰两者是天敌关系。
  find 操作：
• 更新d 数组：按照最基础的距离更新的⽅式， d[x] = d[x] + d[fa[x]] ；
  union 操作：
• 如果x 和y 是同类，那么边权就是0 ；
• 如果x 吃y ，那么边权就是1

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

const int N = 5e4 + 10;

int n, k;
int fa[N], d[N]; //带权并查集

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

    int t = find(fa[x]);
    d[x] += d[fa[x]];
    return fa[x] = t;
}

void un(int x, int y, int w)
{
    int fx = find(x), fy = find(y);
    if (fx != fy)
    {
        fa[fx] = fy;
        d[fx] = d[y] + w - d[x];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;

    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;        
    }

    int ret = 0;
    while (k--)
    {
        int op, x, y; cin >> op >> x >> y;
        int fx = find(x), fy = find(y);
        
        if (x > n || y > n) ret++;
        else if (op == 1) //同类
        {
            if (fx == fy && ((d[y] - d[x]) % 3 + 3) % 3 != 0) ret++;
            else un(x, y, 0);
        }
        else //x -> y
        {
            if (fx == fy && ((d[y] - d[x]) % 3 + 3) % 3 != 1) ret++;
            else un(x, y, 2);
        }
    }
    cout << ret << endl;
    
    return 0;
}

P1196 [NOI2002] 银河英雄传说 - 洛谷

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

const int N = 3e4 + 10;

int n = 3e4;
int fa[N], d[N], cnt[N]; //维护集合的合并，权值，大小

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

    int t = find(fa[x]);
    d[x] += d[fa[x]];
    return fa[x] = t;
}

void un(int x, int y)
{
    int fx = find(x), fy = find(y);

    if (fx != fy)
    {
        fa[fx] = fy;
        d[fx] = cnt[fy];
        cnt[fy] += cnt[fx];
    }
}

int query(int x, int y)
{
    int fx = find(x), fy = find(y);

    if (fx != fy) return -1;
    else return abs(d[y] - d[x]) - 1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
        cnt[i] = 1;
    }
    
    int T; cin >> T;
    while (T--)
    {
        char op; int x, y;
        cin >> op >> x >> y;
        if (op == 'M')
        {
            un(x, y);
        }
        else
        {
            cout << query(x, y) << endl;
        }
    }
    
    return 0;
}