社区讨论

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 条回复,欢迎继续交流。

正在加载回复...