扩展域并查集(求匹配问题)

CF741C

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128=__int128;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using db = double;
using ldb = long double;
#define F first
#define S second
const int N=2e5+10;
pii s[N][2];
void init(int n){
    for(int i=0;i<=n;i++){
        for(int j=0;j<2;j++){
            s[i][j]={i,j};
        }
    }
}
pii find(int x,int y){
    if(s[x][y]==(pii){x,y}) return {x,y};
    return s[x][y]=find(s[x][y].F,s[x][y].S);
}
void merge(int x,int y){
    pii rtx=find(x,0),rty=find(y,1);
    s[rty.F][rty.S]=rtx;
    rtx=find(x,1),rty=find(y,0);
    s[rty.F][rty.S]=rtx;
}
void solve(){
    int n;cin>>n;
    init(n*2);
    for(int i=1;i<=n*2;i+=2){
        merge(i,i+1);
    }
    vector<pii> a(n+1);
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        a[i]={x,y};
        merge(x,y);
    }
    for(int i=1;i<=n;i++){
        auto [x,y]=a[i];
        if(find(x,0).S==0) cout<<2<<" ";
        else cout<<"1 ";
        if(find(y,0).S==0) cout<<"2\n";
        else cout<<"1\n";
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0;
}

P_2024_NOI_2001_食物链

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128=__int128;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using db = double;
using ldb = long double;
#define F first
#define S second
const int N=1e5+10;
pii s[N][3];
void init(int n){
    for(int i=0;i<=n;i++){
        for(int j=0;j<3;j++){
            s[i][j]={i,j};
        }  
    }
}
pii find(int x,int y){
    if(s[x][y]==(pii){x,y}) return {x,y};
    return s[x][y]=find(s[x][y].F,s[x][y].S);
}
bool merge(int x,int y,int op){
    if(op==1){
        pii rtx=find(x,0),rty=find(y,0);
        if(rtx.F==rty.F&&rtx.S!=rty.S) return false;
        s[rty.F][rty.S]={rtx.F,rtx.S};
        rtx=find(x,1),rty=find(y,1);
        s[rty.F][rty.S]={rtx.F,rtx.S};
        rtx=find(x,2),rty=find(y,2);
        s[rty.F][rty.S]={rtx.F,rtx.S};
    }else{
        pii rtx=find(x,0),rty=find(y,1);
        if(rtx.F==rty.F&&rtx.S!=rty.S) return false;
        s[rty.F][rty.S]={rtx.F,rtx.S};
        rtx=find(x,1),rty=find(y,2);
        s[rty.F][rty.S]={rtx.F,rtx.S};
        rtx=find(x,2),rty=find(y,0);
        s[rty.F][rty.S]={rtx.F,rtx.S};
    }
    return true;
}
void solve(){
    int n,k;cin>>n>>k;
    int ans=0;
    while(k--){
        int op,x,y;cin>>op>>x>>y;
        if(x>n||y>n){
            ans++;
            continue;
        }
        if(op==2&&x==y){
            ans++;
            continue;
        }
        bool mark=merge(x,y,op);
        if(!mark) ans++;
    }
    cout<<ans<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int t=1;
    // cin>>t;
    init(1e5);
    while(t--) solve();
    return 0;
}