题解：P3367 【模板】并查集

Lonely_Peak · 2025-03-17 19:47:08 · 题解

并查集

在正式开始写程序之前，我们先来了解一下并查集。

并查集是一种精巧而实用的数据结构,它主要用于处理一些不相交集合的合并问题。经典的应用有连通图、最小生成树 Kruskal 算法、最近公共祖先(LCA)等。并查集在算法竞赛中极为常见。

初步了解

• 并查集的概念：将编号分别为 1 \sim n 的 n 个对象划分为不相交集合,在每个集合中,选择其中某个元素代表所在集合

• 并查集的基本操作、并査集的合并优化、并查集的查询优化--路径压缩和带权并查集。

• 并查集的基本应用是集合问题。在加上权值之后，利用并查集的合并优化和路径压缩可以对权值所代表的具体应用进行高效的操作。

并查集的操作

• 初始化

  • 定义 int s[] 是以结点 i 为元素的并查集。
  • 初始化：令 s[i]=i。

• 合并

  • 要合并两棵树，我们只需要将一棵树的根节点连到另一棵树的根节点。

    void dsu::unite(size_t x, size_t y) {
    pa[find(x)] = find(y);
    }

• 查找

  • 查找元素的集，是一个递归的过程，直到元素的值和它的集相等，就找到了根结点的集。
  • 这棵搜索树，可能很深，复杂度是 O(n)，变成了一个链表，出现了树的“退化”现象。

• 统计

  • 如果 ~s[i] = i`，这是一个根结点，是它所在的集的代表（帮主）。
  • 统计根结点的数量，就是集的数量。

• 参考代码

  void init_set(){ //初始化
  for(int i = 1; i <= maxn; i++) s[i] = i;
  }
  void union_set(int x, int y){ //合并
  x = find_set(x);
  y = find_set(y);
  if(x != y) s[x] = s[y];
  }
  int find_set(int x){ //查找（递归）
  return x==s[x]? x:find_set(s[x]);
  }

解题思路

那么当我们已经基本了解并查集以后，完成这道题就非常简单了。

在这道题，题目要求我们实现两个操作：

• 合并操作：将两个元素所在的集合合并。
• 查询操作：查询两个元素是否在同一个集合中。

根据上面的介绍，合并操作就是一个：

dist[find(p2)] = find(p3);

查询操作就是一个：

if (find(p2) == find(p3)) cout << "Y\n";
else cout << "N\n";

别忘了 find 函数：

int find(int k) {
    if (dist[k] == k) return k;
    return dist[k] = find(dist[k]);
}

参考代码

#include<bits/stdc++.h>
#define int int
#define fast_running ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);
using namespace std;
int n, m, s, ans;
int dist[200005];
int find(int k) {  // 查找操作，带路径压缩
    if (dist[k] == k) return k;
    return dist[k] = find(dist[k]);
}
signed main() {
    fast_running;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) dist[i] = i; // 初始化并查集
    for (int i = 1; i <= m; i++) { // 处理每个操作
        int p1, p2, p3;
        cin >> p1 >> p2 >> p3;
        if (p1 == 1) { // 合并操作
            dist[find(p2)] = find(p3);
        } else { // 查询操作
            if (find(p2) == find(p3)) cout << "Y\n";
            else cout << "N\n";
        }
    }
    return 0;
}

~ 完结撒花 ~