70分求助 谢谢
  • 板块P2078 朋友
  • 楼主CaiYYYYY
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/1/23 19:55
  • 上次更新2024/1/23 22:18:42
查看原帖
70分求助 谢谢
1048863
CaiYYYYY楼主2024/1/23 19:55

答案跟数据点一样但是wa了?


#include <bits/stdc++.h>
using namespace std;
const int N = 20040;
int n, m, p, q;
int cpab[N];

int find(int x) {
	if (cpab[x] != x)
		return cpab[x] = find(cpab[x]);
	return cpab[x];
}


int main() {
	scanf("%d%d%d%d", &n, &m, &p, &q);

	for (int i = 1; i <= n; i++) {
		cpab[i] = i;
	}

	for (int i = 1; i <= m; i++) {
		cpab[i + 10000] = 10000 + i;
	}

	cpab[find(1)] = find(10001);

	for (int i = 0; i < p; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		if (find(a) != find(b))
			cpab[find(a)] = find(b);
	}
	for (int i = 0; i < q; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		a = 10000 - a;
		b = 10000 - b;
		if (find(a) != find(b))
			cpab[find(a)] = find(b);
	}
	int cnt = 0, nn = 0;

	for (int i = 1; i <= N; i++) {
		if (find(i) == find(1)) {
			cnt++;
			if (i > 0 && i <= 10000)
				nn++;
			if (i > 10000)
				nn--;
		}
	}
	nn = abs(nn);
	cnt -= nn;
//	printf("%d\n", cnt);
	printf("%d", cnt / 2);
	return 0;
}
2024/1/23 19:55
加载中...