算法学习专栏——并查集

一、合并集合（简单+）

一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。

现在要进行 m 个操作，操作共有两种：

M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；

输入格式

第一行输入整数 n 和 m。

接下来 m 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

输出格式

对于每个询问指令 Q a b，都要输出一个结果，如果 a 和 b 在同一集合内，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1≤n,m≤10^5^

输入样例：

输出样例：

1
2
3

Yes
No
Yes

思路

直播（录屏）

代码

答案（请自己先思考一下再参考）

        
#include < iostream>
#include < algorithm>
using namespace std;
const int N = 1e5 + 10;
int p[N];
int n, m;
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 0; i < m; i++) {
        char op[2];
        int x, y;
        cin >> op >> x >> y;
        if (op[0] == 'M') {
            p[find(x)] = find(y);            
        } else {
            if (find(x) == find(y)) cout << "Yes\n";
            else cout << "No\n";
        }
    }  
    return 0;
}

二、连通块中点的数量（简单++）

给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。

现在要进行 m 个操作，操作共有三种：

C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
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≤10^5^

输入样例：

输出样例：

1
2
3

Yes
2
3

思路

直播（录屏）

代码

答案（请自己先思考一下再参考）

        
#include < iostream>
#include < algorithm>
using namespace std;
const int N = 1e5 + 10;
int p[N], s[N];
int n, m;
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    char op[3];
    cin >> n >> m;
    for(int i = 1; i <= n; i++) 
    {
        p[i] = i;
        s[i] = 1;
    }
    for (int i = 0; i < m; i++) {
        cin >> op;
        if (op[0] == 'C') {
            int x, y;
            cin >> x >> y;
            if (find(x) == find(y)) continue;
            s[find(x)] += s[find(y)];
            p[find(y)] = find(x);
        } else if (op[1] == '1') {
            int x, y;
            cin >> x >> y;
            if (find(x) == find(y)) cout << "Yes\n";
            else cout << "No\n";
        } else {
            int x;
            cin >> x;
            cout << s[find(x)] << '\n';
        }
    }  
    return 0;
}

三、食物链（中等+）

动物王国中有三类动物 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 句话有的是真的，有的是假的。

当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

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

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

输入格式

第一行是两个整数 N 和 K，以一个空格分隔。

以下 K 行每行是三个正整数 D，X，Y两数之间用一个空格隔开，其中 D 表示说法的种类。

若 D=1=1，则表示 X 和 Y 是同类。

若 D=2=2，则表示 X 吃 Y。

输出格式

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

数据范围

1≤N≤50000
0≤K≤1000000

输入样例：

输出样例：

思路

直播（录屏）

有疑点抓紧时间问本人。

代码

答案（请自己先思考一下再参考）

        
#include < iostream>
#include < algorithm>
using namespace std;
const int N = 5e5 + 10;
int p[N], d[N];
int n, k, ans;
int find(int x){
    if (p[x] != x) {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> k;   
    for (int i = 1; i <= n;i++) p[i] = i;    
    for (int i = 0; i < k; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        if (b > n || c > n) ans++;
        else {
            int pb = find(b),pc = find(c); 
            if (a == 1) {
                if (pb == pc && (d[b] - d[c]) % 3) ans++;
                else if (pb != pc) {
                    p[pb] = pc;
                    d[pb] = d[c] - d[b];
                }
            } else {
                if (pb == pc && (d[b] - d[c] - 1) % 3) ans++;
                else if (pb != pc) {
                    p[pb] = pc;
                    d[pb] = d[c] - d[b] + 1; 
                }
            }    
        }       
    }    
    cout << ans;    
    return 0;
}

算法练习专栏算法小扩展01——秦九昭算法（选看）上一篇

算法学习专栏——spfa 下一篇