并查集的实现_牛客题霸_牛客网

描述

给定一个没有重复值的整形数组arr，初始时认为arr中每一个数各自都是一个单独的集合。请设计一种叫UnionFind的结构，并提供以下两个操作。

boolean isSameSet(int a, int b): 查询a和b这两个数是否属于一个集合

void union(int a, int b): 把a所在的集合与b所在的集合合并在一起，原本两个集合各自的元素以后都算作同一个集合

[要求]

如果调用isSameSet和union的总次数逼近或超过O(N)，请做到单次调用isSameSet或union方法的平均时间复杂度为O(1)

输入描述：

第一行两个整数N, M。分别表示数组大小、操作次数 接下来M行，每行有一个整数opt 若opt = 1，后面有两个数x, y，表示查询(x, y)这两个数是否属于同一个集合 若opt = 2，后面有两个数x, y，表示把x, y所在的集合合并在一起

输出描述：

对于每个opt = 1的操作，若为真则输出"Yes"，否则输出"No"

示例1

输入：

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

复制

输出：

No Yes Yes

复制

说明：

每次2操作后的集合为 ({1}, {2}, {3}, {4}) ({1}, {2, 3}, {4}) ({1, 2, 3}, {4})

备注：

1 \leqslant N, M \leqslant 10^61⩽N,M⩽106

保证1 \leqslant x, y \leqslant N保证1⩽x,y⩽N

1.

递归转化为迭代,_find的递归写法转化为迭代的写法.

递归的出口是father[i]==i,所以while循环的入口在递归的出口条件前面加上一个!取反.

递归的进入下一层本来是_find(father[i]).转化为迭代就是i=father[i].

中间清理栈的迭代过程也可以想象成是递归的过程.

#include<bits/stdc++.h> // 引入常用的头文件
#define int long long // 定义int为长整型，以支持大数据量的处理
#define endl '\n' // 定义换行符为'\n'，增加输出速度
#define p pair< long long, long long> // 定义pair类型的别名p，用于存储两个长整型的数值

using namespace std; // 使用标准命名空间

const int dx[] = { 1, -1, 0, 0 }; // 定义数组dx，用于某些方向操作，此处可能未使用
const int dy[] = { 0, 0, 1, -1 }; // 定义数组dy，用于某些方向操作，此处可能未使用

// 全局变量定义区域
int n, m; // n表示数组大小，m表示操作次数
int op, nums1, nums2; // op操作类型，nums1和nums2操作数

vector<int> father; // 并查集数组，存储每个元素的父节点
vector<int> _stack; // 辅助栈，用于路径压缩

int _find(int i) { // 并查集查找操作，带路径压缩
    while (!(father[i] == i)) { // 如果i不是自己的父节点，进行路径压缩
        i = father[i];
        _stack.push_back(i); // 将当前节点添加到栈中
    }

    while (_stack.size()) { // 当栈不为空时，进行路径压缩
        father[_stack.back()] = i; // 将栈中的每个元素的父节点设置为根节点i
        _stack.pop_back(); // 弹出栈顶元素
    }

    return i; // 返回根节点
}

int isSameSet(int x, int y) { // 检查两个元素是否属于同一个集合
    return _find(x) == _find(y); // 通过查找根节点来判断
}

void _union(int x, int y) { // 并查集合并操作
    if (_find(x) == _find(y)) { // 如果x和y已经属于同一个集合，则不操作
        return;
    } else {
        father[_find(x)] = _find(y); // 将x的根节点的父节点设置为y的根节点，完成合并
    }
}

void init() { // 读取操作和操作数
    cin >> op >> nums1 >> nums2;
}

void solveinit() { // 初始化解决方案，此处未使用
}

void solve() { // 根据操作类型执行相应的并查集操作
    solveinit();
    if (op == 1) { // 如果是查询操作
        if (isSameSet(nums1, nums2))cout << "Yes" << endl; // 如果属于同一个集合，输出"Yes"
        else cout << "No" << endl; // 否则输出"No"
    } else { // 如果是合并操作
        _union(nums1, nums2); // 合并nums1和nums2所在的集合
    }
}

signed main() { // 主函数
    ios::sync_with_stdio(false); // 禁用C和C++的同步，加速cin和cout
    cin.tie(nullptr); // 解除cin和cout的绑定
    cout.tie(nullptr);
    cout << fixed << setprecision(15); // 设置浮点数输出的精度
    cin >> n >> m; // 读入数组大小和操作次数

    father.assign(n + 1, 0); // 初始化father数组，大小为n+1
    for (int i = 0; i <= n; i++) { // 将每个元素的父节点初始化为自己
        father[i] = i;
    }

    while (m--) { // 读取m个操作并执行
        init();
        solve();
    }
}

【模板】并查集 - 洛谷

【模板】并查集

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 $$N,$$ ,表示共有 $$$$ 个元素和 $$$$ 个操作。

接下来 $$$$ 行，每行包含三个整数 $$Z_i,X_i,Y_$$ 。

当 $$Z_i=$$ 时，将 $$X_$$ 与 $$Y_$$ 所在的集合合并。

当 $$Z_i=$$ 时，输出 $$X_$$ 与 $$Y_$$ 是否在同一集合内，是的输出

Y ；否则输出 N 。

输出格式

对于每一个 $$Z_i=$$ 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

样例 #1

样例输入 #1

4 7 2 1 2 1 1 2 2 1 2 1 3 4 2 1 4 1 2 3 2 1 4

样例输出 #1

N Y N Y

提示

对于 $$30\$$ 的数据，$N \le 10$，$M \le 20$。

对于 $$70\$$ 的数据，$N \le 100$，$M \le 10^3$。

对于 $$100\$$ 的数据，$1\le N \le 10^4$，$1\le M \le 2\times 10^5$，$1 \le X_i, Y_i \le N$，$Z_i \in \{ 1, 2 \}$。

#include<bits/stdc++.h> // 引入常用的头文件
#define int long long // 定义int为长整型，适用于处理大数据
#define endl '\n' // 定义结束符为'\n'，优化输出效率
#define p pair<long long, long long> // 定义pair的别名p，用于存储长整型的键值对

using namespace std;

const int dx[] = {1, -1, 0, 0}; // 方向数组，可能用于处理四方向问题，本代码未用到
const int dy[] = {0, 0, 1, -1}; // 方向数组，可能用于处理四方向问题，本代码未用到
//----------------------------------------------------

int n, m; // n是元素数量，m是操作次数
int op, nums1, nums2; // op是操作类型，nums1和nums2是操作的元素

vector<int> father; // 并查集的父节点数组
vector<int> _st; // 辅助栈，用于路径压缩

int _find(int i) { // 查找根节点，并应用路径压缩
    while (!(father[i] == i)) { // 如果节点i不是自己的父节点，继续向上查找
        _st.push_back(i); // 将当前节点加入栈中
        i = father[i]; // 移动到父节点
    }

    while (_st.size()) { // 路径压缩，将路径上的所有节点直接连接到根节点
        father[_st.back()] = i;
        _st.pop_back();
    }

    return i; // 返回根节点
}

bool isSameSet(int x, int y) { // 判断两个元素是否在同一集合中
    return _find(x) == _find(y);
}

void _union(int x, int y) { // 合并两个集合
    if (_find(x) == _find(y)) { // 如果已经在同一集合中，则无需合并
        return;
    } else {
        father[_find(x)] = _find(y); // 否则，将一个集合的根节点指向另一个集合的根节点
    }
}

// 初始化函数，读取输入并初始化并查集
void init() {
    cin >> n >> m;
    father.assign(n + 1, 0); // 分配并初始化并查集数组
    for (int i = 0; i <= n; i++) {
        father[i] = i; // 初始化时，每个元素的父节点是自己
    }
}

// 根据操作类型执行相应的并查集操作
void solve() {
    if (op == 1) { // 如果是合并操作
        _union(nums1, nums2);
    } else { // 如果是查询操作
        if (isSameSet(nums1, nums2)) cout << "Y" << endl; // 如果在同一集合，输出Y
        else cout << "N" << endl; // 否则输出N
    }
}

signed main() {
    ios::sync_with_stdio(false); // 提高cin和cout的效率
    cin.tie(nullptr); // 解绑cin和cout
    cout.tie(nullptr);
    cout << fixed << setprecision(15); // 设置浮点数精度
    //----------------------------------------------
    init(); // 初始化
    while (m--) { // 处理每个操作
        cin >> op >> nums1 >> nums2;
        solve();
    }
}

结尾

最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。

同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。

谢谢您的支持，期待与您在下一篇文章中再次相遇！