UVALive - 3644X-Plosives（并查集）

本文主要是介绍UVALive - 3644X-Plosives（并查集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：UVALive - 3644X-Plosives（并查集）

题目大意：给出K个简单的化合物，正好包含K种元素，那么将它们装车的时候，已经拿到的化合物再来的时候就应该拒绝装车，安全起见，然后给你装车的化合物列表，问你需要拒绝装车的次数。

解题思路：并查集。将已经装过的化合物记录下来，那么如果下次的化合物如果已经在集合中了，就说明需要拒绝装车。

代码：

#include <cstdio>
#include <cstring>const int maxn = 1e5 + 5;
int p[maxn];void init () {for (int i = 0; i < maxn; i++)p[i] = i;
}int getParent(int a) {return a == p[a] ? a: p[a] = getParent (p[a]);
}int main () {int a, b;int ans;while (scanf ("%d", &a) == 1) {ans = 0;init();do {scanf ("%d", &b);int q1 = getParent(a);int q2 = getParent(b);if (q1 == q2)ans++;else p[q1] = q2;} while (scanf ("%d", &a) && a != -1);printf ("%d\n", ans);}return 0;
}

这篇关于UVALive - 3644X-Plosives（并查集）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---