本文主要是介绍LA3644 X-Plosives，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这题是刘汝佳书中的并查集范例，我使用了《挑战程序设计竞赛》书上提供的并查集模板。当我们读到一道题的时候，在读懂题意后应该思考这个问题适用于哪种数据模型，并通过经验来判断使用何种算法，而不是无头苍蝇乱撞。
大致题意：每次给并查集中的数字使用一个并集操作，前提是这两个数字目前并不在同一个集合之中。可能比较含糊，看给出的测试用例：
1 2
3 4
3 5
3 1
2 3
4 1
2 6
6 5
-1一点点来分析：1, 2并集操作，3, 4并集操作，3, 5并集。此时有两个集合，一个是(1, 2)，另一个是(3, 4, 5)。不再赘述，以下每一行代表一次并集操作后的集合状态：
(1, 2) (3, 4, 5)
(1, 2, 3, 4, 5)
(1, 2, 3, 4, 5) // 2 3在同一个集合里，所以不可以装sum++
(1, 2, 3, 4, 5) // 4 1在同一个即合理，所以不可以装sum++
(1, 2, 3, 4, 5, 6)
(1, 2, 3, 4, 5, 6) // 6 5在同一个集合里，不可以装sum++由此得到了数字3。
代码如下：
#define LOCAL#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N = 100000 + 10;
int _par[MAX_N]; // 父亲
int _rank[MAX_N]; // 树的高度// 初始化n个元素
void init(int n)
{for (int i = 0; i < n; i++){_par[i] = i;_rank[i] = 0;}
}// 查询树的根
int find(int x)
{if (_par[x] == x)return x;elsereturn _par[x] = find(_par[x]);
}// 合并x和y所属的集合
void unite(int x, int y)
{x = find(x);y = find(y);if (x == y) return;if (_rank[x] < _rank[y]) {_par[x] = y;}else {_par[y] = x;if (_rank[x] == _rank[y])_rank[x]++;}
}// 判断x和y是否属于同一个集合
bool same(int x, int y)
{return find(x) == find(y);
}
int main()
{
#ifdef LOCALfreopen("input.txt", "r", stdin);
#endifint a, b;while (cin >> a) {init(MAX_N);int res = 0;while (a != -1) {cin >> b;// 如果两个药品属于同一个if (same(a, b))res++;elseunite(a, b);cin >> a;}cout << res << endl;}return 0;
}
上述解释已经很清楚了，不再罗嗦
这篇关于LA3644 X-Plosives的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
