并查集（专题）
解题报告：看似像博弈论的问题，其实就是在询问当两个点在一个集合了就结束游戏了，并查集处理就行了。
#include<iostream>
using namespace std;
const int N=210,M=N*N;
int p[M];
int n,m;
int get(int x,int y)
{
return x*n+y;
}
int find(int x)
{
if(p[x]!=x)
p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>n>>m;
for(int i=0;i<M;i++)
p[i]=i;
int res=0;
for(int i=1;i<=m;i++)
{
int x,y;
char str[2];
cin>>x>>y;
cin>>str;
x--;
y--;
int t=get(x,y);
int t2;
if(str[0]=='D')
{
t2=get(x+1,y);
}
else
{
t2=get(x,y+1);
}
if(find(t2)==find(t))
{
res=i;
break;
}
else
{
p[find(t2)]=find(t);
}
}
if(!res) puts("draw");
else cout<<res<<endl;
return 0;
}
解题报告：这种题其实就可以把一个集合的物品一起打包，然后做一遍01背包就行了。
#include<iostream>
#include<cstring>
using namespace std;
const int N=10010;
int p[N];
int v[N];
int w[N];
int f[N];
int find(int x)
{
if(x!=p[x])
p[x]=find(p[x]);
return p[x];
}
int main()
{
int n,m,W;
cin>>n>>m>>W;
for(int i=1;i<=n;i++)
p[i]=i;
for(int i=1;i<=n;i++)
{
int a,b;
cin>>a>>b;
v[i]=b,w[i]=a;
}
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
int pa=find(a),pb=find(b);
if(pa!=pb)
{
p[pb]=pa;
v[pa]+=v[pb];
w[pa]+=w[pb];
}
}
for(int i=1;i<=n;i++)
if(p[i]==i)
for(int j=W;j>=w[i];j--)
f[j]=max(f[j],f[j-w[i]]+v[i]);
cout<<f[W]<<endl;
return 0;
}
解题报告：这种题先做一遍离散化，因为这些数1~1e9太大了，用hash来做，手写hash哦。
#include<iostream>
#include<cstring>
using namespace std;
const int N=2000003;
int p[N];
int h[N],e[N],ne[N];
int idx;
int find(int x)
{
if(x!=p[x])
p[x]=find(p[x]);
return p[x];
}
struct node{
int a;
int b;
int c;
}edge[N];
void insert(int x)
{
int t=(x%N+N)%N;
e[idx]=x,ne[idx]=h[t],h[t]=idx++;
}
bool find1(int x)
{
int t=(x%N+N)%N;
for(int i=h[t];~i;i=ne[i])
{
int j=e[i];
if(j==x)
return true;
}
return false;
}
int hash1(int x)
{
int t=(x%N+N)%N;
for(int i=h[t];~i;i=ne[i])
{
if(e[i]==x)
return i;
}
}
int main()
{
int T;
cin>>T;
while(T--)
{
memset(h,-1,sizeof h);
idx=0;
int cnt=0;
int n;
for(int i=0;i<=N-1;i++)
p[i]=i;
cin>>n;
for(int i=0;i<n;i++)
{
int a,b,c;
cin>>a>>b>>c;
if(!find1(a))
insert(a);
if(!find1(b))
insert(b);
edge[i]={
hash1(a),hash1(b),c};
if(c==1)
{
int pa=find(hash1(a));
int pb=find(hash1(b));
p[pa]=pb;
}
}
bool flag=true;
for(int i=0;i<n;i++)
{
if(edge[i].c==0)
{
int pa=find(edge[i].a);
int pb=find(edge[i].b);
if(pa==pb)
{
flag=false;
break;
}
}
}
if(!flag) puts("NO");
else puts("YES");
}
return 0;
}
解题报告：这题就要想一想了，告诉你l和r，这个区间的和是否为偶，我们可以依据这个来判断s[r]和s[l-1]之间的奇偶相对性，然后用带权并查集或者扩展域并查集做就行了。
带权并查集：
#include<iostream>
#include<cstring>
#include<unordered_map>
using namespace std;
const int N=20010;
int p[N];
int d[N];
unordered_map<long long,int>S;
int cnt;
int find(int x)
{
if(x!=p[x])
{
int root=find(p[x]);
d[x]=(d[x]+d[p[x]])%2;
p[x]=root;
}
return p[x];
}
int get_id(int x)
{
if(!S.count(x))
S[x]=++cnt;
return S[x];
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<N;i++)
p[i]=i;
int res=m;
for(int i=1;i<=m;i++)
{
int a,b;
int type =0;
string t;
cin>>a>>b>>t;
a=get_id(a-1);
b=get_id(b);
int pa=find(a);
int pb=find(b);
if(t=="odd") type = 1;
if(pa!=pb)
{
d[pa]=(d[b]-d[a]+type)%2;
p[pa]=pb;
}
else
{
if(((d[a]-d[b])%2+2)%2!=type)
{
res=i-1;
break;
}
}
}
cout<<res<<endl;
return 0;
}
扩展域：
#include<iostream>
#include<cstring>
#include<unordered_map>
using namespace std;
const int N=40010,base=N/2;
int p[N];
unordered_map<int,int>S;
int cnt;
int find(int x)
{
if(x!=p[x])
p[x]=find(p[x]);
return p[x];
}
int get_id(int x)
{
if(!S.count(x))
S[x]=++cnt;
return S[x];
}
int main()
{
int n,m;
cin>>n>>m;
n=0;
for(int i=1;i<N;i++)
p[i]=i;
int res=m;
for(int i=1;i<=m;i++)
{
int a,b;
int type =0;
string t;
cin>>a>>b>>t;
a=get_id(a-1);
b=get_id(b);
if(t=="odd") type = 1;
if(type)
{
if(find(a)==find(b))
{
res=i-1;
break;
}
p[find(a)]=find(b+base);
p[find(a+base)]=find(b);
}
else
{
if(find(a+base)==find(b))
{
res=i-1;
break;
}
p[find(a)]=find(b);
p[find(a+base)]=find(b+base);
}
}
cout<<res<<endl;
return 0;
}
解题报告：维护一个d数组，d代表到根节点的距离，每次查询根节点之间距离就是abs(d[a]-d[b])-1,如果a和b同一个点那就输出0就行了。每次合并的时候让合并的点加上前面船的数量。
#include<bits/stdc++.h>
using namespace std;
const int N=30010;
int d[N],p[N],Size[N];
int find(int x)
{
if(x!=p[x])
{
int root=find(p[x]);
d[x]+=d[p[x]];
p[x]=root;
}
return p[x];
}
int main()
{
int m;
cin>>m;
for(int i=1;i<N;i++)
p[i]=i,Size[i]=1;
while(m--)
{
char op[2];
int a,b;
cin>>op>>a>>b;
// cout<<op<<endl;
int pa=find(a);
int pb=find(b);
if(op[0]=='M')
{
// cout<<a<<' '<<b<<endl;
p[pa]=pb;
d[pa]=Size[pb];
Size[pb]+=Size[pa];
}
else
{
// cout<<pa<<' '<<pb<<endl;
if(pa!=pb)
puts("-1");
else
{
cout<<max(0,abs(d[a]-d[b])-1)<<endl;
}
}
}
return 0;
}
扩展域写法：
#include<iostream>
#include<cstring>
using namespace std;
const int N=150010;
int p[N];
int find(int x)
{
if(p[x]!=x)
p[x]=find(p[x]);
return p[x];
}
int main()
{
int n,k;
cin>>n>>k;
for(int i=0;i<N;i++)
p[i]=i;
int res=0;
while(k--)
{
int op,a,b;
cin>>op>>a>>b;
if(op==2&&a==b)
{
res++;
continue;
}
if(a>n||b>n)
{
res++;
continue;
}
if(op==1)
{
int pa=find(a),pb=find(b);
if(find(a)==find(b+n)||find(a+n)==find(b)) //a是b的天敌，或者b是a的天敌
{
res++;
continue;
}
p[find(a)]=find(b);
p[find(a+n)]=find(b+n);
p[find(a+2*n)]=find(b+2*n);
}
else
{
if(find(a)==find(b)||find(b)==find(a+n)) //b是a的天敌，或者a和b是同类
{
res++;
continue;
}
p[find(a)]=find(b+n);
p[find(a+n)]=find(b+2*n);
p[find(a+2*n)]=find(b);
}
}
cout<<res<<endl;
return 0;
}
查看18道真题和解析