6-1 并查集
///find函数可能有点难理解,自己尝试画下图随便理解好吧
///M是合并,Q是询问是否在一个树中
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n,m;
int q[N];
int find(int x)
{
if(q[x]!=x) q[x]=find(q[x]));///如果x不是树的头结点,向上循环查找到头结点为止.
///可以自己画图理解一下;
return q[x];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
q[i]=i;
while(m--)
{
char op[2];
int a,b;
scanf("%s%d%d",&op,&a,&b);
if(op[0]=='M') q[find(a)]=find(b);
else
{
if(find(a)==find(b))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
return 0;
}
6-2 查并集,但是可能输出长度
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m;
int p[N],size[N];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
p[i]=i;
size[i]=1;
}
while(m--)
{
///C为合并,Q1为 检查是否在同一区间,Q2检查长度;
char op[2];
scanf("%s",&op);
int a,b;
if(op[0]=='C')
{
cin>>a>>b;
if(find(a)==find(b)) continue;///特判
size[find(b)]+=size[find(a)];
p[find(a)]=find(b);
}
else if(op[1]=='1')
{
cin>>a>>b;
if(find(a)==find(b))
cout<<"YES"<<endl;
else
cout<<"No"<<endl;
}
else if(op[1]=='2')
{
cin>>a;
cout<<size[find(a)]<<endl;
}
}
}
6-3 食物链
https://www.luogu.com.cn/problem/P2024
///这题是真难,看视频加理解一共花了俩小时
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m,res=0;
int p[N],d[N];
int find(int x)
{
if(p[x]!=x)///与以往不同,这里的d数组刚开始的作用是,x节点与父节点的距离,经过find函数递归之后
///d数组变成了,x节点到头节点的距离,这样就可以来判断是不是同一类和接下来做题了
{
int t=find(p[x]);
d[x]+=d[p[x]];///因为要用到p[x],所以先储存;
p[x]=t;
}
return p[x];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
p[i]=i;
while(m--)
{
int a,b,c;
cin>>c>>a>>b;
if(a>n||b>n) res++;
else
{
if(c==1)
{
int pa=find (a),pb=find(b);
if(pa==pb&&(d[a]-d[b])%3) res++;///3个一循环;如果A和B是同类,而且他俩已经在合并过了,那么两者的距离相减,如果余三不得0那么就是错的;
else
{
p[pa]=pb;
d[pa]=d[b]-d[a];
}
}
else
{
int pa=find(a),pb=find(b);
if(pa==pb&&(d[a]-d[b]-1)%3) res++;
else if(pa!=pb)
{
p[pa]=pb;
d[pa]=d[b]+1-d[a];
}
}
}
}
cout<<res;
return 0;
}
6-4 自动程序检测装置
https://www.luogu.com.cn/problem/P1955
///这个题是我得知有查并集这个算法的起初
///查并集+离散化,题目i和j都开到10的九次方了,不用离散化等着爆吧
///本题思路
#include<bits/stdc++.h>
using namespace std;
const int N=400010;
int t,n;
int a[2*N],p[N],d[2*N],b[N],c[N];
int find(int x)///典
{
if(p[x]!=x)
p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[2*i-1]>>a[2*i]>>c[i];
d[2*i-1]=a[2*i-1],d[2*i]=a[2*i];
}
sort(d+1,d+2*n+1);
int h=0;
b[0]=-1;
for(int i=1;i<=2*n;i++)
if(b[h]!=d[i]) b[++h]=d[i];///离散化完成,用了两次这个离散化模板了,感觉yxc老师的那个离散化模板用不了一点
for(int i=1;i<=h;i++)
p[i]=i;///更新爹节点
for(int i=1;i<=n;i++)
{
if(c[i]==0)
continue;
int x=lower_bound(b+1,b+h+1,a[2*i-1])-b;
int y=lower_bound(b+1,b+h+1,a[2*i])-b;
if(find(x)==find(y)) continue;
else
p[find(x)]=find(y);///将所有相等的元素,放进树里面;接下来的就是狠狠的查找有没有内鬼
}
bool f=false;
for(int i=1;i<=n;i++)
{
if(c[i]==1)
continue;
int x=lower_bound(b+1,b+h+1,a[2*i-1])-b;
int y=lower_bound(b+1,b+h+1,a[2*i])-b;
if(find(x)==find(y))///查找内鬼,如果有人在相等的树里面,就是内鬼!
{
cout<<"NO"<<endl;
f=true;
break;
}
}
if(!f)
cout<<"YES"<<endl;
}
return 0;
}
6-6 A-bugs
http://bailian.openjudge.cn/practice/2492/
///此题考察并查集的应用,考察的是加权并查集,类似于食物链,需要考虑两者之间存在距离关系
///大题思路:每当输出两个数字是,代表这两个数字之间肯定是异性关系(如果两者满足距离为奇数)
///每当新的数加入到另一个树上时,如果符合条件,那么就意味这两者的距离之差至少为1,并且都是奇数,再向下拓展一位,也就是距离为偶数的,就是同性
///可以用da-db%2来判断,如果两者在一个树上并且满足这个条件,这两个人就是同性!
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n,m,t;
int p[N],d[N];
int find(int x)
{
if(x!=p[x])
{
int t=find(p[x]);
d[x]+=d[p[x]];
p[x]=t;
}
return p[x];
}
int main()
{
cin>>t;
int res=1;
while(t--)
{
cin>>n>>m;
for(int i=1;i<=n;i++)
p[i]=i;
memset(d,0,sizeof d);
bool f=false;
while(m--)
{
int a,b;
cin>>a>>b;
int pa=find(a),pb=find(b);
if(pa==pb&&(d[a]-d[b])%2==0)
f=true;
else
{
p[pa]=p[b];
d[pa]=d[b]+1-d[a];
}
}
if(f)
{
printf("Scenario #%d:\n",res++);
cout<<"Suspicious bugs found!"<<endl;
}
else
{
printf("Scenario #%d:\n",res++);
cout<<"No suspicious bugs found!"<<endl;
}
cout<<endl;
}
return 0;
}
标签：int,res,查集,cin,pb,pa,find From： https://www.cnblogs.com/o-Sakurajimamai-o/p/17427994.html