牛客算法竞赛入门课第四节习题 Part2（并查集扩展）
牛客算法竞赛入门课第四节习题 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;
}
