板子
先说一下并查集
- 将两个集合合并
- 查询两个元素是否在一个集合
基本原理：每个集合用一颗数来表示。树根的编号就是震哥哥集合的编号，每个节点存储ta的父节点，p[x]表示x的父节点
- f(p[x]==x) x就是父节点
- 如果不是父节点 while(p[x] != x)p[x]=x;继续向上寻找
- 合并两个集合，就把其中一个树根节点的p[x]改为另一个树根节点的编号 p[x]=x p[y]=y --> p[x]=y;
优化：把父节点直接都改为数根结点，压缩找到数根结点的深度
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
const int N = 1e5+10;
int p[N];
int n,m;
int find(int x)
{
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)p[i]=i;
while(m--)
{
string x;
int a,b;
cin>>x>>a>>b;
if(x=="M")p[find(a)]=find(b);
else
{
if(find(a)==find(b))puts("Yes");
else puts("No");
}
}
return 0;
}
习题
1. Wireless Network POJ - 2236
题目链接：Wireless Network POJ - 2236
题意：有n台电脑，给他们的 (x,y) 坐标
两台电脑可以通信的条件
- 两台电脑是完好的，具有通信功能
- 两者距离不超过d
工作人员现在有两种操作 - 修好电脑x
- 询问x和y电脑是否可以通信
分析：使用并查集，用通信将电脑划分为两个集合，可以通信的电脑放在一个集合，不可以放在另一个集合
每次修好一个电脑后，遍历可以通信的电脑是否距离小于d可以划分到可以通信的集合里
每次询问两个电脑可不可以通信，看是不是在通信的集合中
ps：初始化
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 1100;
int n,d;
int p[N];
int x[20001],y[20001];
bool vis[N];
int fin(int x)
{
if(p[x]!=x)p[x]=fin(p[x]);
return p[x];
}
double Dis(int i,int j)
{
double xx=x[i]-x[j];
double yy=y[i]-y[j];
return sqrt(xx*xx+yy*yy);
}
int main()
{
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++)
p[i]=i,scanf("%d%d",&x[i],&y[i]);
string o;
while(cin>>o)
{
int a,b;
int c=0;
if(o=="O")
{
cin>>a;
vis[a]=true;
if(c==0)c=a;
else p[fin(a)]=fin(c);
for(int i=1;i<=n;i++)
if(vis[a]&&vis[i]&&Dis(a,i)<=d)p[fin(i)]=fin(a);
}
else
{
cin>>a>>b;
if(vis[a]&&vis[b]&&fin(a)==fin(b))puts("SUCCESS");
else puts("FAIL");
}
}
return 0;
}
2. The Suspects POJ - 1611
题目链接：The Suspects POJ - 1611
题意：给n个人，m个小组，问含有0号的集合里的人数
分析：并查集板子，每个小组和成一个集合，最后遍历p数组统计同一集合的人数
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 3e4+100;
int n,m;
int p[N];
int fin(int x)
{
if(p[x]!=x)p[x]=fin(p[x]);
return p[x];
}
int main()
{
while(scanf("%d%d",&n,&m))
{
if(n==0&&m==0)break;
for(int i=0;i<=n;i++)p[i]=i;
while(m--)
{
int k,x,xx;
scanf("%d%d",&k,&xx);
for(int i=2;i<=k;i++)
{
scanf("%d",&x);
int a=fin(xx),b=fin(x);
p[b]=a;
}
}
int res=1,index=fin(0);
for(int i=1;i<=n;i++)
if(index==fin(p[i]))res++;
printf("%d\n",res);
}
return 0;
}
3. A Bug’s Life POJ - 2492
题目链接：A Bug’s Life POJ - 2492
题意：n只虫子，m个关系，问关系里存不存在矛盾
分析：带权？并查集 每个关系是x和y性别相异，不一定谁男谁女，存下来对立关系，如果出现x和y同一集合，则出现矛盾，否则将x放入y的对立集合，将y放入x的对立集合
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 4100;
int p[N],re[N];
int n,m,t,o=0;
int fin(int x)
{
if(p[x]!=x)p[x]=fin(p[x]);
return p[x];
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)p[i]=i,re[i]=0;
bool flag=false;
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
int a=fin(x),b=fin(y);
if(a==b)
flag=true;
if(re[a])p[fin(re[a])]=b;
else re[a]=b;
if(re[b])p[fin(re[b])]=a;
else re[b]=a;
}
printf("Scenario #%d: \n",++o);
if(flag)puts("Suspicious bugs found!");
else puts("No suspicious bugs found!");
printf("\n");
}
}
4. 集合问题
题目链接：集合问题
题意：现在有n个数，将n个数放入a和b集合条件是
- 当x在A集合，a-x必须在A集合
- 当y在B集合，b-y必须在B集合
分析：记录每个数的位置，A集合连到0，B集合连到n+1，并且优先放b（决定if的顺序），最后输出
若序列中存在b-x，则将x和b-x放到一起
若序列中存在a-x，则将x和a-x放到一起
放到一起这个操作就是并查集
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#define fr(i,k,n) for(int i=k;i<=n;i++)
using namespace std;
const int N = 1e5+10;
int p[N];
int s[N];
int n,a,b,mx=0;
map<int,int>ma;
int fin(int x)
{
if(p[x]!=x)p[x]=fin(p[x]);
return p[x];
}
int main()
{
scanf("%d%d%d",&n,&a,&b);
bool flag=true;
fr(i,0,n+1)p[i]=i;
fr(i,1,n)
{
int o,e,ee;
scanf("%d",&s[i]);
ma[s[i]]=i;
mx=max(mx,s[i]);
}
if(mx>max(a,b))flag=false;
fr(i,1,n)
{
if(ma[b-s[i]])
p[fin(i)]=fin(ma[b-s[i]]);
else p[fin(i)]=fin(0);
if(ma[a-s[i]])
p[fin(i)]=fin(ma[a-s[i]]);
else p[fin(i)]=fin(n+1);
}
int e=fin(0);
int ee=fin(n+1);
if(e==ee)flag=false;
if(flag)
{
printf("YES\n");
fr(i,1,n)
{
if(e==fin(i))printf("0");
else printf("1");
if(i<n)printf(" ");
}
}
else
{
printf("NO\n");
}
return 0;
}
|