连通块＆＆食物链——（并查集小结）

目录

1、并查集三个最基本的流程

2、并查集的主要操作

3、例题（1）来喽——连通块的数量

4、例题（2）来喽——食物链（带权并查集）

5、基于食物链对带权并查集的分析

---

1、并查集三个最基本的流程

一、将两个集合进行合并；

二、询问两个元素是否在同一个集合当中；

三、所在某个集合中的元素个数；

2、并查集的主要操作

 一、寻找祖宗节点（路径优化）；

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);//路径优化
    //通过路径优化直接找到X的祖宗结点
    return p[x];
    //while(x!=p[x]) x=p[x];  基础版本
    //不优可能因为树的深度过深，耗费大量时间
}

二、合并a、b所在的两个集合并算出元素个数（有易错点！！！）

int x = find(a), y = find(b); 
if (x != y)
{
   p[x] = y;
   s[x] += s[y]; //执行合并计算集合内元素的个数
}

//下面是错误的版本
if(find(a) != find(b))
{
   p[find(a)] = find(b);
   s[find(b)] += s[find(a)];
}
//这两个看起来一样，并没有什么区别，但是仔细一想，却别有洞天
//下面这个是错误的，很容易被绕晕

细品！！！当时我就在这里卡了好久，楞是不知道错哪了。需要仔细想明白！

上面第二种情况：p[find(a)] = find(b)后，a和b的根节点是同一个，find(a) == find(b)（原来的find(a)消失了），s[find(b)] += s[find(a)]就等价于s[find(b)] *= 2，此时就发生了错乱。也就相当于可以把   s[find(b)] += s[find(a)]放到前面，把p[find(a)] = find(b)放到后面就对了。

上面第一种情况：p[a] = find(b)后，a == find(a)，b == find(b)，此时原来的find(a)还在，所以s[b] += s[a]加上的还是原来的s[find(a)]。

3、例题（1）来喽——连通块的数量

题目描述

给定一个包含 n 个点（编号为 1~n ）的无向图，初始时图中没有边。
现在要进行 m 个操作，操作共有三种：

1. C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
2. Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
3. Q2 a，询问点 a 所在连通块中点的数量。

输入格式

第一行输入一个整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为 C a b ，Q1 a b 或 Q2 a 中的一种。

输出格式

对于每个询问命令 Q1 a b，如果 a 和 b 在同一连通块中，则输出 Yes，否则输出 No。
对于每个询问指令 Q2 a，输出一个整数表示点 a 所在连通块中点数量。
每个结果占一行

数据范围

1 <= n,m <= 1e5

样例输入

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

样例输出

Yes
2
3

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 1e6 + 10;
int n, m, p[N], s[N];

int find(int x)
{
	if (x != p[x]) p[x] = find(p[x]);//路径优化
	return p[x];
}
int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) p[i] = i, s[i] = 1;
	while (m--)
	{
		char op[2];
		int a, b;
		scanf("%s", &op);
		if (op[0] == 'C')
		{
			scanf("%d %d", &a, &b);
			if (find(a) != find(b))//注意了！易错点！！
			{
				s[find(b)] += s[find(a)];//先认清楚亲戚
				p[find(a)] = find(b);//再改变祖宗
			}
		}
		if (op[1] == '1')
		{
			scanf("%d %d", &a, &b);
			if (find(a) == find(b)) printf("Yes\n");
			else printf("No\n");
		}
		if (op[1] == '2')
		{
			scanf("%d", &a);
			printf("%d\n", s[find(a)]);
		}
	}
	return 0;
}

4、例题（2）来喽——食物链（带权并查集）

题目描述

动物王国中有三类动物A、B、C，这三类动物的食物链构成了有趣的环形。
A吃B，B吃C，C吃A。
现有N个动物，以 1~N 编号。
每个动物都是A，B，C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这 N 个动物所构成的食物链关系进行描述：
第一种说法是 1 X Y ，表示 X 和 Y 是同类。
第二种说法是 2 X Y ，表示 X 吃 Y。
此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。
当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1. 当前的话与前面的某些真的话冲突，就是假话；
2. 当前的话中 X 或 Y 比 N 大，就是假话；
3. 当前的话表示 X 吃 X ，就是假话。

你的任务是根据给定的 N 和 K 句话，输出假话的总数。

输入格式

第一行是两个整数 N 和 K，以一个空格分隔。
以下 K 行每行是三个整数D，X，Y，两数之间用一个空格隔开，其中 D 表示说法的种类。
若 D = 1，则表示 X 和 Y 是同类。只有一个整数，表示假话的数目。
若 D = 2，则表示 X 吃 Y。

输出格式

只有一个整数，表示假话的数目

样例输入

100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

样例输出

3

数据范围

1 <= N <= 50000
0 <= K <= 100000

5、基于食物链对带权并查集的分析

一、带权并查集思路

只要他们有关系，就属于同一个集合，就把他们加入到集合中去（不管是同类或者异类），因此并查集所属的边带权值的问题本质上是在维护一个大的集合（其他的都是单个点，然后逐一加到大集合里）。因此也就是说只要两个元素在同一个集合里，就能通过他们与根节点的距离知道他们之间的关系（%取模）；

二、关于递归调用与距离计算的顺序

下面是两种不同的递归（乍一看一样，但却相差很大）
<1>int find(int x)
{
    if(p[x] != x)
    {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}


当时我也在想，下面的好像操作更简单，但为什么就一直错呢
<2>int find(int x)
{
    if(p[x] != x)
    {
        d[x] += d[p[x]];//错误就在此处的p[x]上(无路径压缩)
        p[x] = find(p[x]);
    }
    return p[x];
}

原因分析：

1、第二种递归代码中d[x]最开始是指x到父节点的距离，如果没有路径压缩，那么d[p[x]]指的是p[x]到其父节点的距离，那么第二种递归的实际意义就变成了：d[x] = d[x] + d[p[x]]——x到根节点的距离 = x到父节点的距离 + 父节点到父节点的距离（错误就出现在这里了）因为父节点的父节点不一定是根节点，导致距离计算错误。

！！！

2、第一种递归代码中首先进行了路径压缩（int t = find(p[x]），然后 d[x] = d[x] + d[p[x]]——就变成了：x到根节点的距离 = x到父节点的距离 + 父节点到根节点的距离，只有先进行find()函数，d[p[x]] 才是父节点到根节点的距离。没进行find()则只是p[x]到p[p[x]]的距离罢了，而并不是到p[x]的根结点的距离。

三、关于食物链关系的计算（来自y总的图）

1.当x和y是同类的时候（分为在一个集合和不在一个集合两种）

2、.当x吃y的时候（分为在一个集合和不在一个集合两种）

#include <iostream>
#include<algorithm>

using namespace std;

const int N = 50010;
int n, m;
int p[N], d[N];

int find(int x)
{
    if (p[x] != x)// 如果x不是根节点
    {
        // 这个find语句执行完以后，p[x]到根节点的距离都更新了。
        int t = find(p[x]);
        //x到根节点的距离 = x到父节点的距离 + 父节点到根节点的距离
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) p[i] = i;
    int res = 0;
    while (m--)
    {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);

        if (x > n || y > n) res++;
        else
        {
            int px = find(x), py = find(y);
            if (t == 1)// x和y是同类
            {
               
                if (px == py && (d[x] - d[y]) % 3!=0) res++; // 注意取模的技巧
                else if (px != py)
                {
                    // 合并成同类，x所在的集合合到y所在的集合里边。
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else// x吃y
            {
                if (px == py && (d[x] - d[y] - 1) % 3!=0) res++;
                else if (px != py)
                {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }
    printf("%d\n", res);
    return 0;
}