n,m<=5e4;
首先操作 2 用并查集就行了. 题解说的好啊!
考虑操作一, 连的两个点如果同色, 直接合并, 然后这个颜色的联通块 - 1, 然后合并 bitset, 就是或一下. bitset 维护的是相连的异色结点.
如果两个点异色, 那么我们就不管他们, 直接在两个 bitset 里分别把对方设为 1.
对于操作三 直接 (b[x]&b[y]).count(); 就行了.
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 5e4+5;
- int fa[N];
- bitset<50001> b[N];
- int find(int a){
- return a==fa[a]?a:fa[a]=find(fa[a]);
- }
- int n,m,op,x,y,c[N];
- int main(){
- iOS::sync_with_stdio(false);
- cin>>n>>m;
- int hei=0,bai;
- for(int i=1;i<=n;i++){
- fa[i]=i;cin>>c[i];
- hei+=c[i];
- }
- bai=n-hei;
- while (m--){
- cin>>op;
- if(op==1){
- cin>>x>>y;
- int xx=x,yy=y;
- x=find(x);y=find(y);
- if(x==y)continue;
- if(c[xx]==1){
- if(c[yy]==1)fa[y]=x,hei--,b[x]|=b[y];
- else b[x][yy]=1,b[y][xx]=1;
- } else{
- if(c[yy]==0)fa[y]=x,bai--,b[x]|=b[y];
- else b[x][yy]=1,b[y][xx]=1;
- }
- } else if(op==2){
- cin>>x;
- if(!x)cout<<bai<<endl;
- else cout<<hei<<endl;
- } else{
- cin>>x>>y;
- x=find(x);y=find(y);
- if(x==y)cout<<-1<<endl;
- else{
- cout<<(b[x]&b[y]).count()<<endl;
- }
- }
- }
- }
- View Code
来源: http://www.bubuko.com/infodetail-2949061.html