并查集的题
关于带有多个相对集合的全集，我们可以多开几倍的空间。每一倍的元素表示这个当前里的相对元素
#include#include #include using namespace std;int f[600000];int find(int x){ if(f[x]==x) return x; return f[x]=find(f[x]);}int _union(int x,int y){ int f1=find(x),f2=find(y); f[f1]=f2;}int main(){ int n,k; scanf("%d%d",&n,&k); int a,b,c; for(int i=1;i<=3*n;i++) f[i]=i; int t=0; for(int i=1;i<=k;i++) { scanf("%d%d%d",&a,&b,&c); if(b>n||c>n) { t+=1; continue; } if(a==1) { if(find(b+n)==find(c)||find(b+2*n)==find(c)) { t+=1; continue; } _union(b,c); _union(b+n,c+n); _union(b+2*n,c+2*n); } if(a==2) { if(b==c) { t+=1; continue; } if(find(b+n)==find(c)||find(b)==find(c)) { t+=1; continue; } _union(b+2*n,c); _union(b,c+n); _union(b+n,c+2*n); } } printf("%d",t);}
肯定有一些自恃NB的不会看的