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 4Output 
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();}
}