80分求调并查集

#include <bits/stdc++.h>
#define int long long
//标记切分属性 每一次选择最大的切分属性来切分
int m,n,k,l,d;
const int MAXN = 1e3+10;
int father[MAXN*2];
int a[MAXN][MAXN];
int cnt_idx[MAXN];
int cnt_col[MAXN];
void build(int n){
    for(int i=1;i<=n;i++){
        father[i]=i;
    }
}
int find(int i){
    if(father[i]!=i){
        father[i]=find(father[i]);
    }
    return father[i];
}
void Union(int x,int y){
    int fx = find(x);
    int fy = find(y);
    if(fx!=fy){
        father[fx]=fy;
    }
}
void printarr(){
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            std::cout<<a[i][j]<<" ";
        }
        std::cout<<'\n';
    }
    std::cout<<'\n';
    for(int i=1;i<=m;i++){
        std::cout<<cnt_idx[i];
    }
    std::cout<<'\n';
    for(int j=1;j<=n;j++){
        std::cout<<cnt_col[j];
    }
}
struct Node{
    int num,id;
};
struct cmp{
    bool operator()(const Node& n1,const Node& n2){
        return n1.num<n2.num;
    }
};
inline void run(){
    std::cin>>m>>n>>k>>l>>d;
    //k 横着
    //l 竖着
    //d 有多少对
    int cnt=1;
    build(d);
    for(int i=0,x1,y1,x2,y2;i<d;i++){
        std::cin>>x1>>y1>>x2>>y2;
        if(a[x1][y1]==0&&a[x2][y2]==0){
            a[x1][y1]=cnt;
            a[x2][y2]=cnt++;
        }else{
            if(a[x1][y1]!=0 && a[x2][y2]==0){
                a[x2][y2]=a[x1][y1];
                continue;
            }
            if(a[x2][y2]!=0 && a[x1][y1]==0){
                a[x1][y1]=a[x2][y2];
                continue;
            }
            Union(a[x1][y1],a[x2][y2]);
        }

    }
    for(int i=1;i<m;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]==a[i+1][j] && a[i][j]!=0 && find(a[i][j])==find(a[i+1][j])){
                cnt_idx[i]++;
            }
        }
    }
    for(int j=1;j<n;j++){
        for(int i=1;i<=m;i++){
            if(a[i][j]==a[i][j+1]&&a[i][j]!=0&&find(a[i][j+1])==find(a[i][j])){
                cnt_col[j]++;
            }
        }
    }
    std::priority_queue<Node,std::vector<Node>,cmp> pq;
    std::vector<int> ans;
    for(int i=1;i<m;i++){
        pq.push({cnt_idx[i],i});
    }
    while(k--){
        ans.push_back(pq.top().id);
        // std::cout<<pq.top().id<<" ";
        pq.pop();
    }
    while(!pq.empty()){
        pq.pop();
    }
    std::sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++){
        if(i==0){
            std::cout<<ans[i];
        }else{
            std::cout<<" "<<ans[i];
        }
    }
    ans.clear();
    std::cout<<'\n';
    for(int j=1;j<n;j++){
        pq.push({cnt_col[j],j});
    }
    while(l--){
        ans.push_back(pq.top().id);
        pq.pop();
    }
    std::sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++){
        if(i==0){
            std::cout<<ans[i];
        }else{
            std::cout<<" "<<ans[i];
        }
    }
    // printarr();
    //idx
    

}
signed main(){
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    // freopen("P1056_2.in","r",stdin);
    int T=1;
    while(T--){
        run();
    }
    return 0;
}