测试了几个都对,洛谷得分30,汗。求大佬帮看一下
  • 板块P1551 亲戚
  • 楼主heiheiwolala
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/1 21:58
  • 上次更新2023/11/2 11:30:02
查看原帖
测试了几个都对,洛谷得分30,汗。求大佬帮看一下
765192
heiheiwolala楼主2023/11/1 21:58
#include<iostream>
#include<vector>
using namespace std;

vector<int> set;
vector<int> rank;

int find(int x) {
    if(set[x]==x) 
        return x;
    else {
        int root = find(set[x]);
        if (set[x]!=root) {
            set[x]=root;
            extern vector<int> rank;
            rank[root]++;
        } 
        return root;
    }
}

void initial(int n){
    for(int i=0;i<n;i++) {
        extern vector<int> set;
        extern vector<int> rank;
        set.push_back(i);
        rank.push_back(i);
    }
}

void build(int x,int y){
    extern vector<int> set;
    extern vector<int> rank;
    int root_x= find(x), root_y = find(y);
    if(rank[root_x]>=rank[root_y]) {
        set[y] = root_x;
    } else {
        set[x] = root_y;
    }
    if(rank[root_x]==rank[root_y]&&root_x!=root_y){
        rank[root_x]++;
    }
}

int main() {
    int n,m,p;
    cin>>n>>m>>p;
    initial(n);
    for(int i=0;i<m;i++) {
        int x,y;
        cin>>x>>y;
        build(x,y);
    }
    for(int i=0;i<p;i++) {
        int x,y;
        cin>>x>>y;
        if(find(x)==find(y)) {
            cout<<"Yes"<<endl;
        } else {
            cout<<"No"<<endl;
        }
    }
}

2023/11/1 21:58
加载中...