并查集

并查集（Union-find Sets）是一种非常精巧而实用的数据结构，它主要用于处理一些不相交集合的合并问题。一些常见的用途有：求连通子图、求最小生成树的Kruskal算法和求最近公共祖先（LCA）等。

并查集的基本操作

• 1.初始化init

• 2.查询find

• 3.合并unionn

  //用数组fa[]来存储每个元素的父节点
  int fa[MAXN];
  //一开始，我们先将它们的父节点设为自己
  void init(int n)
  {
  for(int i=1;i<=n;i++)
  fa[i]=i;
  }
  //查询 找到i的祖先就返回
  int find(int i)
  {
  if(fa[i]==i) return i; //递归出口，当到达了祖先位置,就返回祖先
  else
  {
  fa[i]=find(fa[i]); //路径压缩
  return findfa[i]; //不断向上查找祖先
  }

  }
  void unionn(int i,int j)
  {
  int i_fa=find(i);
  int j_fa=find(j);
  fa[i_fa]=j_fa; //i的祖先指向j的祖先
  }

亲戚

P1551 亲戚 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目背景

若某个家族人员过于庞 大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

题目描述

规定：x 和 y 是亲戚，y 和 z 是亲戚，那么 x 和 z 也是亲戚。如果 x，y 是亲戚，那么 x 的亲戚都是 y 的亲戚，y 的亲戚也都是 x 的亲戚。

输入格式

第一行：三个整数 n,m,p，（n_,m,p≤5000），分别表示有 n 个人，m* 个亲戚关系，询问 _p 对亲戚关系。

以下 m 行：每行两个数 i j，表示 i 和 j 具有亲戚关系。

接下来 p 行：每行两个数 P_i,P_j，询问 P_i和 P_j 是否具有亲戚关系。

输出格式

p 行，每行一个 Yes 或 No。表示第 i 个询问的答案为“具有”或“不具有”亲戚关系。

输入输出样例

输入 #1复制

6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6

输出 #1复制

Yes
Yes
No


#include<iostream>
using namespace std;
#define MAXN 20001
int fa[MAXN];
//一开始，我们先将它们的父节点设为自己
void init(int n)
{
    for (int i = 1; i <= n; i++)
        fa[i] = i;
}
//查询 找到i的祖先就返回
int find(int i)
{
    if (fa[i] == i) return i; //递归出口，当到达了祖先位置,就返回祖先
    else
    {
        fa[i] = find(fa[i]); //路径压缩
        return fa[i]; //不断向上查找祖先
    }

}
void unionn(int i, int j)
{
    int i_fa = find(i);
    int j_fa = find(j);
    fa[i_fa] = j_fa; //i的祖先指向j的祖先
}

int main()
{
    int n, m, x, y, q;
    cin >> n;
    init(n);
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> x >> y;
        unionn(x, y);
    }
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        cin >> x >> y;
        if (find(x) == find(y))
            cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

任意点

任意点 (nowcoder.com)

题意

平面上有若干个点，从每个点出发，你可以往东南西北任意方向走，直到碰到另一个点，然后才可以改变方向。

请问至少需要加多少个点，使得点对之间互相可以到达。

输入描述

第一行一个整数n表示点数（ 1 <= n <= 100)。

第二行n行，每行两个整数xi, yi表示坐标（ 1 <= xi, yi <= 1000)。

y轴正方向为北，x轴正方形为东。

输出描述

输出一个整数表示最少需要加的点的数目。

解析

这个题目不难，也是一个裸的并查集，不过有一点隐晦，下面解释一下。

首先他只能撞到一个点才能停，看这个图

可以看到1234都是可以相互联系的，而5是独立出来的一个点，要是想要到达5，就要在12或者24之间加一个点，所以这个像什么，就是两个独立的连通块，这样子就很明显是一个并查集了。

这个并查集是当x相同或者y相同的时候，就可以插入在一个块里面。

#include <iostream>
using namespace std;

struct point {
    int x;
    int y;
} p[110];
int fa[110];

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

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

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
        cin >> p[i].x >> p[i].y; //scanf("%d")
    }
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
            if (p[i].x == p[j].x || p[i].y == p[j].y) {
                join(i, j);
            }
        }
    }
    int ans = -1;
    for (int i = 1; i <= n; ++i) {
        if (fa[i] == i)
            ++ans;
    }
    cout << ans << endl;
    return 0;
}