萌新的萌新题求条,马蜂不萌新
  • 板块P2078 朋友
  • 楼主Ruan_ji
  • 当前回复4
  • 已保存回复5
  • 发布时间2024/7/7 21:03
  • 上次更新2024/7/8 07:48:01
查看原帖
萌新的萌新题求条,马蜂不萌新
405146
Ruan_ji楼主2024/7/7 21:03

样例一直输出3,不到是为什么呀?

#include <iostream>
#include <cstdio>

#define MAXN 100005

using namespace std;

int n, m, p, q;
int fa[MAXN * 2], fb[MAXN * 2];

int find1(int x) {
	if (fa[x + MAXN] == x) {
		return x;
	}
	return fa[x + MAXN] = find1(fa[x+MAXN]);
}

void merge1(int x, int y) {
	x = find1(x); y = find1(y);
	fa[y + MAXN] = x;
	return ;
}

int find2(int x) {
	if (fb[x + MAXN] == x) {
		return x;
	}
	return fb[x + MAXN] = find2(fb[x + MAXN]);
}

void merge2(int x, int y) {
	x = find2(x); y = find2(y);
	fb[y + MAXN] = x;
	return ;
}

int main() {
	cin >> n >> m >> p >> q;
	for (int i = 1; i <= n; ++i) {
		fa[i + MAXN] = i;
		fb[i + MAXN] = i;
	}
	for (int i = 1; i <= p; ++i) {
		int x, y;
		cin >> x >> y;
		
		if (find1(x) != find1(y))
			merge1(x, y);
	}
	for (int i = 1; i <= q; ++i) {
		int x, y;
		cin >> x >> y;
		
		if (find2(x) != find2(y))
			merge2(x, y);
	}
	
	int cnt1 = 0, cnt2 = 0;
	int aa = find1(1 + MAXN);
	for (int i = 1 + MAXN; i <= n + MAXN; ++i) {
		if (find1(i) == aa) {
			cnt1 ++;
		}
	}
	
	int bb = find2(-1 + MAXN);
	for (int i = -m + MAXN; i <= -1 + MAXN; ++i) {
		if (find2(i) == bb) {
			cnt2 ++;
		}
	}
	
	cout << min(cnt1, cnt2) << endl;
	return 0;
}

3Q斯密达

2024/7/7 21:03
加载中...