并查集,但是找不到哪一步出错
  • 板块学术版
  • 楼主ww4445
  • 当前回复8
  • 已保存回复8
  • 发布时间2021/6/14 04:29
  • 上次更新2023/11/4 21:54:24
查看原帖
并查集,但是找不到哪一步出错
406728
ww4445楼主2021/6/14 04:29

可能是晚上太累了吧。。。对着测试数据半天没看出来哪一步错了(。_。)

#include <iostream>
#include <string>
using namespace std;

const int N = 1e5 + 10;
int n, m, a, b, node[N], order[N];
string ope;

int anc(int a) {
    if(node[a] == a) return a;
    else return node[a] = anc(node[a]);
}
void setEdge(int a, int b) {
    int a1 = anc(a);
    int b1 = anc(b);
    order[b1] += order[a1];
    node[a1] = b1;
}
void quiOne(int a, int b) {
    if(anc(a) == anc(b)) cout << "Yes" << endl;
    else cout << "No" << endl;
}
void quiTwo(int a) {
    cout << order[anc(a)] << endl;
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) {
        node[i] = i;
        order[i] = 1;
    }
    while(m --) {
        cin >> ope >> a;
        if(ope == "C") {
            cin >> b;
            setEdge(a, b);
        }
        else if(ope == "Q1") {
            cin >> b;
            quiOne(a, b);
        }
        else {
            quiTwo(a);
        }
    }
}
2021/6/14 04:29
加载中...