011.并查集

并查集

#include<vector>
using namespace std;

class UnionFind{
    vector<int>fa;
    public:
    //初始化
    UnionFind(int n):fa(n){
        for(int i=0;i<n;i++)fa[i]=i;
    }
    //查找父节点
    int find(int x){
        if(x!=fa[x])return fa[x]=find(fa[x]);//路径压缩
        return fa[x];
    }
    void merge(int a,int b){
        int A=find(a);
        int B=find(b);
        if(A!=B)fa[A]=B;//避免成环
    }
    bool check(int a,int b){
        return find(a)==find(b);
    }
};

一道例题

Input
5 5 6
1 2
2 3
2 4
2 5
4 5
3
1 1 2
3
2 1 2
1 2 4
2 2 4

Output 
0
1
NO
YES

观察数据范围，得知我们需要离线处理

先读入所有边和所有操作

初始建图 ：连上那些永远不会被删的边

倒着处理所有操作，维护连通分量数目cnt

收集答案，最后倒着输出答案

操作 3 ：ans = 连通分量(cnt) - 1

操作 2 ：查询连通

操作 1 ：连接 x , y 连通成功 cnt --

#include<bits/stdc++.h>
using namespace std;
namespace IO{template<typename T>void read(T&x){x=0;bool f=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}if(f)x=-x;}void read(char&c){c=getchar();while(isspace(c))c=getchar();}void read(string&s){s.clear();char ch=getchar();while(isspace(ch))ch=getchar();while(!isspace(ch)&&ch!=EOF){s+=ch;ch=getchar();}}template<typename T,typename...Args>void read(T&first,Args&...rest){read(first);read(rest...);}template<typename T>void wr(T x){if(x==0){putchar('0');return;}if(x<0){putchar('-');x=-x;}char stk[20];int top=0;while(x){stk[++top]=x%10+'0';x/=10;}while(top){putchar(stk[top--]);}}void wr(const char c){putchar(c);}void wr(const string&s){for(char c:s)putchar(c);}void wr(const char*s){while(*s)putchar(*s++);}template<typename T>void wr(const T&x,char sep){wr(x);putchar(sep);}template<typename T,typename...Args>void wr(const T&first,const Args&...rest){wr(first);((putchar(' '),wr(rest)),...);}}using namespace IO;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const int MAXN=100005;
class UnionFind{
    vector<int>fa;
    public:
    //初始化
    UnionFind(int n):fa(n){
        for(int i=0;i<n;i++)fa[i]=i;
    }
    //查找父节点
    int find(int x){
        if(x!=fa[x])return fa[x]=find(fa[x]);//路径压缩
        return fa[x];
    }
    void merge(int a,int b){
        int A=find(a);
        int B=find(b);
        if(A!=B)fa[A]=B;//避免成环
    }
    bool check(int a,int b){
        return find(a)==find(b);
    }
};
void solve(){
    int n,m,q;
    read(n,m,q);
    vector<pii>e;
    map<pii,int>de;
    int mode,u,v;
    for(int i=0;i<m;++i){
        read(u,v);
        u--,v--;
        if(u>v)swap(u,v);
        e.push_back({u,v});
        de[{u,v}]=INF;
    }
    vector<pair<int,pii>>op(q);
    for(int i=0;i<q;++i){
        read(mode);
        op[i].first=mode;
        if(mode!=3){
            read(u,v);
            u--,v--;
            if(u>v)swap(u,v);
            op[i].second={u,v};
            if(mode==1)de[{u,v}]=i;
        }
    }
    UnionFind UF(n);
    int cnt=n;
    for(auto &x:e){
        if(de[x]==INF){
            u=x.first;
            v=x.second;
            if(!UF.check(u,v))cnt--;
            UF.merge(u,v);
        }
    }
    vector<int>ans;
    for(int i=q-1;i>=0;i--){
        u=op[i].second.first;
        v=op[i].second.second;
        if(op[i].first==3)ans.push_back(cnt-1);
        else if(op[i].first==2){
            if(UF.check(u,v))ans.push_back(-101);
            else ans.push_back(-100);
        }
        else{
            if(!UF.check(u,v))cnt--;
            UF.merge(u,v);
        }
    }
    for(int i=ans.size()-1;i>=0;i--){
        int x=ans[i];
        if(x==-101)wr("YES\n");
        else if(x==-100)wr("NO\n");
        else wr(x,'\n');
    }
}
int main(){
    int T=1;
    //read(T);
    while(T--){
        solve();
    }
}