社区讨论
30 分求好心人帮助修改 急急急!!!
P2078朋友参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lo3deg1o
- 此快照首次捕获于
- 2023/10/24 04:48 2 年前
- 此快照最后确认于
- 2023/10/24 04:48 2 年前
CPP
#include<stdio.h>
#include <math.h>
int n, m, p, q;
int pre1[50010],pre2[50010];
int num1 = 1, num2 = 1;
int g = 1, h = 1;
int find1(int x) {
if (x == pre1[x])return x;
else { g++;
return pre1[x] = find1(pre1[x]);
}
}
int find2(int x) {
if (x == pre2[x])return x;
else {
h++; return pre2[x] = find2(pre2[x]);
}
}
void joint1(int x,int y) {
int a = find1(x);
int b = find1(y);
if (a != b) {
if (a == 1 && b != 1 || b == 1 && a != 1) num1 += g;
g = 1;
if (b == 1)
pre1[a] = b;
else pre1[b] = a;
}
}
void joint2(int x, int y) {
int a = find2(x);
int b = find2(y);
if (a != b) {
if (a == 1&&b!=1 || b == 1&&a!=1) num2 += h;
h = 1;
if (b == 1)pre2[a] = b;
else pre2[b] = a;
}
}
int main() {
scanf("%d %d %d %d", &n, &m, &p, &q);
for (int i = 1; i <= 50000; i++) {
pre1[i] = i;
pre2[i] = i;
}
int a, b;
for (int i = 1; i <= p; i++) {
scanf("%d %d", &a, &b);
joint1(a, b);
}
for (int i = 1; i <= q; i++) {
scanf("%d %d", &a, &b);
joint2(abs(a),abs(b));
}
if (num1 > num2)printf("%d", num2);
else printf("%d", num1);
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...