云智第四节学习记录
第四节-并查集及其技巧（种类并查集，带权并查集，可撤销并查集，扩展域并查集，启发式合并，按秩合并）
- 第四节题单
A 题：P3367 【模板】并查集
板题，切掉了。
清朝代码如下：
#include<bits/stdc++.h>
using namespace std;
int sets[1000000];
int find(int x){
if(sets[x]!=x)sets[x]=find(sets[x]);
return sets[x];
}
void unoin(int &x,int &y){
x=find(x),y=find(y);
sets[x]=y;
}
bool nouoi(int x,int y){
if(find(x)==find(y))return true;
else return false;
}
int main() {
int q,m;
cin>>q>>m;
for(int i=1;i<=q;i++)sets[i]=i;
for(int i=0;i<m;i++){
int x,y,z;
cin>>x>>y>>z;
if(x==1)unoin(y,z);
else {
if(nouoi(y,z))cout<<"Y\n";
else cout<<"N\n";
}
}
return 0;
}B 题：P1955 [NOI2015] 程序自动分析
一点思维罢了。
清朝代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn=3E6+5;
const int mod=2999999;
int t;
int n,cnt;
struct st {
int x,y,k;
} a[maxn];
vector<pair<int,int> > mp[maxn];
void Insert(int x) {
for(int i=0; i<mp[x%mod].size(); i++) {
if(mp[x%mod][i].first==x)return ;
}
mp[x%mod].push_back(make_pair(x,++cnt));
}
int Hash(int x) {
for(int i=0; i<mp[x%mod].size(); i++) {
if(mp[x%mod][i].first==x) {
return mp[x%mod][i].second;
}
}
}
int f[maxn];
int Find(int x) {
if(x==f[x])return x;
return f[x]=Find(f[x]);
}
void Merge(int x,int y) {
x=Find(x);
y=Find(y);
if(x==y)return ;
f[x]=y;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--) {
bool flag=0;
for(int i=0; i<mod; i++)mp[i].clear();
cnt=0;
cin>>n;
for(int i=1; i<=n; i++) {
cin>>a[i].x>>a[i].y>>a[i].k;
Insert(a[i].x);
Insert(a[i].y);
}
for(int i=1; i<=cnt; i++)f[i]=i;
for(int i=1; i<=n; i++) {
int x,y,k;
x=Hash(a[i].x);
y=Hash(a[i].y);
k=a[i].k;
if(k==1) {
Merge(x,y);
}
}
for(int i=1; i<=n; i++) {
int x,y,k;
x=Hash(a[i].x);
y=Hash(a[i].y);
k=a[i].k;
if(k==0) {
if(Find(x)==Find(y)) {
flag=1;
break;
}
}
}
if(flag==1) {
cout<<"NO\n";
} else {
cout<<"YES\n";
}
}
return 0;
}C 题：P1197 [JSOI2008] 星球大战
运用离线算法倒序维护并查集，这题我写过类似的，像关闭农场之类的。
本来可以切掉的，却被卡到凌晨一点，结果无赖对拍时发现是自己范围开小了，难崩。
现代代码如下
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define I_love_Foccarus return
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define deap(i,a,b) for(int i=a;i>=b;i--)
#define in(a) a=read()
const int N = 2e6+5;
const int inf = INT_MAX;
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-48;
ch=getchar();
}
return x*f;
}
void fast() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
struct Edge {
int act,nex;
} edge[N<<2];
int head[N],eid;
void eadd(int u,int v) {
eid++;
edge[eid].act=v,edge[eid].nex=head[u];
head[u]=eid;
}
int fa[N],t[N],st[N],out[N],otop;
int find(int u) {
return fa[u]==u?u:fa[u]=find(fa[u]);
}
int ans;
void dfs(int u) {
for(int i=head[u]; i; i=edge[i].nex) {
int v=edge[i].act;
if(!t[v]&&find(u)!=find(v)) {
fa[find(u)]=find(v);
ans--;
dfs(v);
}
}
}
int k;
int n,m;
signed main() {
//fast();
in(n),in(m);
n--;
rep(i,0,n)fa[i]=i;
rep(i,1,m) {
int x,y;
in(x),in(y);
eadd(x,y),eadd(y,x);
}
in(k);
rep(i,1,k) {
in(st[i]);
t[st[i]]=1;
}
ans=n-k+1;
rep(i,0,n) {
if(!t[i])dfs(i);
}
out[++otop]=ans;
deap(j,k,1) {
ans++,t[st[j]]=0;
for(int i=head[st[j]]; i; i=edge[i].nex) {
int v=edge[i].act;
if(!t[v]&&find(st[j])!=find(v)) {
fa[find(st[j])]=find(v);
ans--;
}
}
head[st[j]]=0;
out[++otop]=ans;
}
while(otop) {
printf("%d\n",out[otop--]);
}
return 0;
}D 题：P2024 [NOI2001] 食物链
种类并查集板题，切了。
现代代码如下
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define deap(i,a,b) for(int i=a;i>=b;i--)
#define in(a) a=read()
const int N = 2e6+5;
const int inf = INT_MAX;
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-48;
ch=getchar();
}
return x*f;
}
void fast() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
int fa[N];
int find(int u) {
return fa[u]==u?u:fa[u]=find(fa[u]);
}
signed main() {
//fast();
int n,k,ans=0;
in(n),in(k);
rep(i,0,n*3) fa[i]=i;
rep(i,1,k) {
int op,x,y;
in(op),in(x),in(y);
if (x>n||y>n) {
ans++;
} else if(op==1) {
if(find(n+x)==find(y)||find(n+y)==find(x)) {
ans++;
} else {
fa[find(x)]=find(y);
fa[find(n+x)]=find(n+y);
fa[find((n<<1)+x)]=find((n<<1)+y);
}
} else {
if (find(x)==find(y)||find(x)==find(n+y)) {
ans++;
} else {
fa[find(n+x)]=find(y);
fa[find((n<<1)+x)]=find(n+y);
fa[find(x)]=find((n<<1)+y);
}
}
}
cout<<ans;
return 0;
}
E 题：P1196 [NOI2002] 银河英雄传说
带权并查集板题，切了。
清朝代码如下
#include<bits/stdc++.h>
using namespace std;
int s[30005];
int d[30005];
int zs[30005];
int find(int i) {
if(s[i]!=i) {
int root=find(s[i]);
d[i]+=d[s[i]];
s[i]=root;
return root;
}
return s[i];
}
void merge(int x,int y) {
int fa=find(x),fb=find(y);
d[fa]+=zs[fb];
s[fa]=fb;
zs[fb]+=zs[fa];
zs[fa]=0;
}
bool access(int x,int y){
if(find(x)==find(y))return true;
else return false;
}
int inquire(int x,int y) {
if(!access(x,y))return -1;
else return abs(d[x]-d[y])-1;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n=30000,m;
cin>>m;
for(int i=1; i<=n; i++)s[i]=i,d[i]=0,zs[i]=1;
for(int i=0; i<m; i++) {
char x;
cin>>x;
if(x=='M') {
int a,b;
cin>>a>>b;
merge(a,b);
} else {
int a,b;
cin>>a>>b;
cout<<inquire(a,b)<<'\n';
}
}
return 0;
}F 题：Destroying Array
采用离线算法，从后往前回复被删除的点，最大连续和可以用带权并查集维护。
现代代码如下
#include<iostream>
#include<cstring>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define deap(i,a,b) for(int i=a;i>=b;i--)
#define in(a) a=read()
const int N = 1e5+5;
const int inf = INT_MAX;
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-48;
ch=getchar();
}
return x*f;
}
void fast() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
int fa[N];
long long ans[N],t[N];
int find(int u) {
return fa[u]==u?u:fa[u]=find(fa[u]);
}
signed main() {
//fast();
int n;
in(n);
int *a=new int[n+1],*b=new int[n+1];
rep(i,1,n)in(a[i]);
rep(i,1,n)in(b[i]);
rep(i,1,n)fa[i]=i;
ans[n]=0;
memset(t,-1,sizeof(t));
deap(i,n-1,1) {
t[b[i+1]]=a[b[i+1]];
if(b[i+1]-1>0&&~t[b[i+1]-1]) {
t[b[i+1]]+=t[find(b[i+1]-1)];
fa[find(b[i+1]-1)]=find(b[i+1]);
}
if(b[i+1]+1<=n&&~t[b[i+1]+1]) {
t[b[i+1]]+=t[find(b[i+1]+1)];
fa[find(b[i+1]+1)]=find(b[i+1]);
}
ans[i]=max(ans[i+1],t[b[i+1]]);
}
rep(i,1,n)printf("%lld\n",ans[i]);
return 0;
}G 题：P3402 可持久化并查集
可持久化并查集板题，某人因为此题再度熬到凌晨一点。可持久化并查集可以通过可持久化数组实现，这也就要使用我们伟大的主席树算法了。
我快速的写完了代码，交了上去，结果——常数被卡了。
考虑优化常数。按秩合并？摆烂，直接随机化吧。
舍伍德算法启动。——依旧被卡。
启发式合并——被卡依旧。
错误的按深度合并——死循环。
现在是北京时间一点一十二分~
\bx 什么意思啊？GTP 改错……
越改越错……
受不了了！睡觉！
刷牙中……
等等，我的一个下标貌似多减了一个1？！！
还真是，AC——qnq。
代码如下：
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define I_love_Foccarus return
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define deap(i,a,b) for(int i=a;i>=b;i--)
#define in(a) a=read()
const int N = 1e6+5;
const int inf = INT_MAX;
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-48;
ch=getchar();
}
return x*f;
}
void fast() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
int tot;
struct Tree {
int l,r,v,sz;
};
Tree t[N<<5];
inline void push_back(Tree x) {
t[++tot]=x;
}
int root[N];
int n,m,a[N],b[N];
int js;
inline int change(int idx,int l,int r,int q,int be) {
Tree tmp=t[idx];
if(l==r) {
tmp.v=be;
push_back(tmp);
return tot;
}
int mid=(l+r)>>1;
if(q<=mid) {
tmp.l=change(tmp.l,l,mid,q,be);
} else {
tmp.r=change(tmp.r,mid+1,r,q,be);
}
push_back(tmp);
return tot;
}
inline int add(int idx,int l,int r,int q) {
Tree tmp=t[idx];
if(l==r) {
tmp.sz++;
push_back(tmp);
return tot;
}
int mid=(l+r)>>1;
if(q<=mid) {
tmp.l=add(tmp.l,l,mid,q);
} else {
tmp.r=add(tmp.r,mid+1,r,q);
}
push_back(tmp);
return tot;
}
inline int query(int idx,int l,int r,int q) {
if(l==r) {
return idx;
}
int mid=(l+r)>>1;
if(q<=mid)return query(t[idx].l,l,mid,q);
else return query(t[idx].r,mid+1,r,q);
}
inline int build(int l,int r) {
Tree tmp;
if(l==r) {
tmp.l=tmp.r=-1,tmp.v=l,tmp.sz=0;
push_back(tmp);
return tot;
}
int mid=(l+r)>>1;
tmp.l=build(l,mid),tmp.r=build(mid+1,r);
tmp.v=tmp.sz=-1;
push_back(tmp);
return tot;
}
int anser;
inline int find(int qt,int u) {
int v=query(root[qt],1,n,u);
if(u==t[v].v)return v;
else return find(qt,t[v].v);
}
signed main() {
//fast();
in(n),in(m);
root[0]=build(1,n);
rep(i,1,m) {
int op,qx,qy,val,l,r;
in(op),in(qx);
if(op==1) {
root[i]=root[i-1];
in(qy);
int fx=find(i,qx),fy=find(i,qy);
if(t[fx].v!=t[fy].v) {
if(t[fx].sz>t[fy].sz)swap(fx,fy);
root[i]=change(root[i-1],1,n,t[fx].v,t[fy].v);
if(t[fx].sz==t[fy].sz)
root[i]=add(root[i],1,n,t[fy].v);
}
} else if(op==2) {
root[i]=root[qx];
} else {
in(qy);
cout<<(find(i-1,qx)==find(i-1,qy))<<'\n';
root[i]=root[i-1];
}
}
return 0;
}