牛客算法竞赛入门课第四节习题 Part2（并查集扩展）

Cube Stacking （带权并查集）

题意：

有1~n个箱子，把箱子看成栈。进行如下操作：把x放在y的栈顶，计算x所表示的栈里在x下面的箱子数。

转化一下就是：连接x和y（有顺序），计算x所在联通块的个数

思路：

维护两个数组，一个表示x联通块的大小，一个表示答案。

连接两个点时

 cnt[x]=num[y];//更新x的答案
 num[y]+=num[x];///合并联通块个数
 root[x]=y;//表示将x移动到y

代码：

#include<cstdio>
#include<cstring>
#include<stdio.h>
#include<iostream>
using namespace std;
const int maxn=30000+10;

int cnt[maxn],num[maxn],root[maxn];

int Find(int x){
    if(x!=root[x]){
        int tmp=Find(root[x]);
        cnt[x]+=cnt[root[x]];
        root[x]=tmp;
        return tmp;
    }
    else return root[x];
}

void Union(int x,int y){
    x=Find(x);y=Find(y);
    if(x!=y){
        cnt[x]=num[y];
        num[y]+=num[x];
        root[x]=y;
    }
}

int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<maxn;i++){
        root[i]=i;
        num[i]=1;
        cnt[i]=0;
    }
    char op[2];
    for(int i=0;i<n;i++){
       scanf("%s",op);
        if(op[0]=='M'){
            int x,y;
            scanf("%d%d",&x,&y);
            Union(x,y);
        }
        else if(op[0]=='C') {
            int x;scanf("%d",&x);
            int t=Find(x);
            printf("%d\n",cnt[x]);
          ///  cout<<cnt[x]<<endl;
        }
    }
    return 0;
}

食物链（扩展域并查集）

思路：

开三个扩展域，即天敌域，同类域，捕食域。

考虑一下错误的情况：

如果x,y是同类，但是x的天敌域或捕食域里有y，错误；

如果x是y的天敌，但是x的同类域或捕食域里有y，错误；

也可以用带权并查集做，但是不是很好推。

代码：（之前写的代码）

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
int fa[200000];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy) fa[fx]=fy;
}
int main(){
    int n,k,i,ans=0;
    int d,x,y;
    scanf("%d%d",&n,&k);
    for(i=0;i<=3*n;i++)
        fa[i]=i;
    for(i=1;i<=k;i++){
        scanf("%d%d%d",&d,&x,&y);
        if(x>n||y>n){
            ans++;
            continue;
        }
        if(d==1){//同类
            if(find(x)==find(y+n)||find(x+n)==find(y)) ans++;//x吃y或y吃x
            else{
                merge(x,y);
                merge(x+n,y+n);
                merge(x+2*n,y+2*n);
            }
        }
        else {//x吃y
            if(x==y||find(x+n)==find(y)||find(x)==find(y)) ans++;//y吃x 或同类
            else{
                merge(x,y+n);
                merge(x+n,y+2*n);
                merge(x+2*n,y);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

程序自动分析（离散化+并查集判冲突）

思路：

并查集判冲突很常见的，但这题的数据范围着实感人。
我们可以对数据进行离散化，离散化通常有两种
（1）保序：排序判重二分
（2）不需要排序：map || hash

然后我们可以先考虑相等约束，在这个过程中是没有矛盾的。然后我们再考虑不等条件若x,y在一种集合里说明存在矛盾

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> PII;
#define I_int ll
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char F[200];
inline void out(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
    //cout<<" ";
}
const int maxn=2e6+7;
int n,m,root[maxn];
unordered_map<int,int>mp;///hash
struct node{
    int x,y,op;
}a[maxn];///存储输入
int push(int x){
    if(!mp.count(x)) mp[x]=++n;
    return mp[x];
}
int Find(int x){
    if(x!=root[x]) root[x]=Find(root[x]);
    return root[x];
}
void Union(int x,int y){
    x=Find(x),y=Find(y);
    if(x!=y) root[x]=y;
}
bool query(int x,int y){
    x=Find(x),y=Find(y);
    if(x==y) return 1;
    return 0;
}
void AC(){
    int t;t=read();
    while(t--){
        m=read();n=0;
        mp.clear();///一定要清零！
        for(int i=1;i<=m;i++){
            int x,y,op;
            x=read();y=read();op=read();
            a[i].x=push(x);a[i].y=push(y);a[i].op=op;
        }
        for(int i=0;i<=n;i++) root[i]=i;///并查集初始化
        for(int i=1;i<=m;i++)
            if(a[i].op) Union(a[i].x,a[i].y);
        bool flag=1;
        for(int i=1;i<=m;i++)
            if(!a[i].op){
                if(query(a[i].x,a[i].y)){
                    flag=0;
                    break;
                }
            }
        if(flag) puts("YES");
        else puts("NO");
    }
}
int main(){
    AC();
    return 0;
}