并查集实践

并查集实践

文章目录

​​是不是亲戚问题​​​​躲避拥堵的最佳路线​​

是不是亲戚问题

我们使用merge的优化，就不使用find的优化了

#include #include using namespace std;int SIZE = 0;int* parent = nullptr; // 记录每个节点的父节点int* height = nullptr; // 记录根节点的层高// 返回x所在树的根节点的编号int find_root(int x) { if (x <= 0 || x >= SIZE) { return -1; } while (x != parent[x]) { x = parent[x]; } return x;}// 合并x和y所在的集合void merge(int x, int y) { x = find_root(x); y = find_root(y); if (x != y) { // 这里x和y都是根节点，谁矮谁作为孩子节点 if (height[x] > height[y]) { parent[y] = x; } else { if (height[x] == height[y]) { // y作为合并以后树的根，根节点高度要+1 height[y]++; } parent[x] = y; } }}int main() { int m = 0; int p = 0; int n = 0; cin >> n >> m >> p; SIZE = n + 1; parent = new int[SIZE]; height = new int[SIZE]; for (int i = 0; i < SIZE; i++) { height[i] = 1; parent[i] = i; // 一开始，每个节点的父节点就是自己 } int p1, p2; // 两个人 for (int i = 0; i < m; i++) { cin >> p1 >> p2; merge(p1, p2); } vector> query; for (int i = 0; i < p; i++) { cin >> p1 >> p2; query.push_back(pair(p1, p2)); } for (auto q : query) { cout << (find_root(q.first) == find_root(q.second) ? "YES" : "NO") << endl; } delete[] parent; delete[] height; parent = nullptr; height = nullptr; return 0;}/*6 5 31 21 53 45 21 31 42 35 6*/

躲避拥堵的最佳路线

3 3 1 3 # 3个区、3条边、从1区到3区1 2 2 # 从1区到2区的拥挤度为22 3 11 3 3

题目说规划一条路径，使得经过道路的拥挤度的最大值最小。该测试用例输出2，是说我们从1区到3区，可以走1->2->3，此时拥挤度的最大值为2；也可以走1->3，此时拥挤度的最大值为3；故该测试用例输出2

我们使用kruskal算法，先从拥挤度小的边开始选取，直到连通s区和t区，这样最后一条选取的边一定是已选道路拥挤度最大的，未选道路拥挤度最小的，这样就能做到在连通的基础上所选取的最大值最小

#include #include #include using namespace std;int* parent = nullptr;struct Edge { Edge(int start, int end, int w) : start_(start) , end_(end) , w_(w) {} int start_; int end_; int w_;};// 找编号为x的节点的根节点int find(int x) { if (x == parent[x]) { return x; } else { // find优化，查找根节点的过程中，把遍历过的节点的父节点都改成根节点 parent[x] = find(parent[x]); return parent[x]; }}int main(){ int n, num_edge, s, t; cin >> n >> num_edge >> s >> t; parent = new int[n + 1](); // n个区，为了让编号和下标对应，多开辟一个 vector edges; int start, end, w; for (int i = 0; i < num_edge; i++) { cin >> start >> end >> w; edges.emplace_back(start, end, w); // 初始化parent数组 parent[start] = start; parent[end] = end; } // 边进行升序排列 sort(edges.begin(), edges.end(), [](const Edge& e1, const Edge& e2) ->bool{ return e1.w_ < e2.w_; }); for (int i = 0; i < num_edge; i++) { int root1 = find(edges[i].start_); int root2 = find(edges[i].end_); if (root1 != root2) { // 根节点不同，可以连接 parent[root1] = root2; if (find(s) == find(t)) { // 选择了新的边，才会判断是否连通了s区和t区；本轮循环没有选择新的边，则没有必要判断是否连通s区和t区 cout << edges[i].w_ << endl; } } } delete[] parent; return 0;}/*3 3 1 31 2 22 3 11 3 3*/

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。