笔记:并查集技巧总结

简介: 笔记:并查集技巧总结

什么是并查集
在计算机科学中,并查集是一种树型的数据结构,用于处理一些不交集(Disjoint Sets)的合并及查询问题。有一个联合-查找算法(Union-find Algorithm)定义了两个用于此数据结构的操作:

Find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union:将两个子集合并成同一个集合。
由于支持这两种操作,一个不相交集也常被称为联合-查找数据结构(Union-find Data Structure)或合并-查找集合(Merge-find Set)。

并查集可以解决什么问题
组团、配对
图的连通性问题
集合的个数
集合中元素的个数

算法模板


using namespace std;
const int N = 1e6 + 6;
int fa[N];
void init(int n)
{
    for (int i = 1; i <= n; i++)
        fa[i] = i;
}
int find(int x)
{
    if (fa[x] == x)
        return x;
    else
        return fa[x] = find(fa[x]);
}
void unionn(int i, int j)
{
    i = find(i);
    j = find(j);
    fa[i] = j;
}
int main()
{
    int n, m;
    cin >> n >> m;
    init(n);
    string s;
    int i, j;
    while (m--)
    {
        cin >> s;
        if (s == "M")
        {
            cin >> i >> j;
            unionn(i, j);
        }
        else
        {
            cin >> i >> j;
            if (find(i) == find(j))
                cout << "Yes" << endl;
            else
                cout << "No" << endl;
        }
    }
    return 0;
}
相关文章
|
5月前
|
存储 算法 C语言
【数据结构与算法 刷题系列】合并两个有序链表
【数据结构与算法 刷题系列】合并两个有序链表
|
6月前
|
算法
刷题专栏(七):将有序数组转换为二叉搜索树
刷题专栏(七):将有序数组转换为二叉搜索树
65 0
|
算法
回溯算法总结笔记
回溯算法总结笔记
|
算法 Java 测试技术
Leetcode刷题笔记:二分查找算法
LeetCode 对于数组查询算法之一的二分查找算法的简单认识。
102 0
|
存储 算法
【数据结构与算法】并查集
【数据结构与算法】并查集
【数据结构与算法】并查集
进阶——细赏并查集(1)
进阶——细赏并查集(1)
157 0
进阶——细赏并查集(1)
08数据结构与算法刷题之【并查集】篇
08数据结构与算法刷题之【并查集】篇
08数据结构与算法刷题之【并查集】篇
|
存储 算法 搜索推荐
数据结构与算法—拓扑排序
拓扑排序,很多人都可能听说但是不了解的一种算法。或许很多人只知道它是图论的一种排序,至于干什么的不清楚。又或许很多人可能还会认为它是一种啥排序。而实质上它是对有向图的顶点排成一个线性序列。
144 0
数据结构与算法—拓扑排序