首页 > 代码库 > 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(并查集)