🎆音乐分享(点击链接可以听哦)
并查集是一种树型的数据结构,用于处理一些不相交集合(DisjointSetsDisjointSets)的合并及查询问题。常常在使用中以森林来表示。
#include <iostream>
using namespace std;
const int N = 100010;
int p[N];
int find(int x)//返回祖宗结点
{
if (p[x] != x) p[x] = find(p[x]);//硬使p[x]=它的祖宗结点
return p[x];
}
int main()
{
int n, m;
cin>>n>>m;
for (int i = 1; i <= n; i ++ ) p[i] = i;//i是p[i]的父结点
while (m -- )
{
char op;
int a, b;
cin>>op>>a>>b;
if (op == 'M') p[find(a)] = find(b);//find[a]:a的祖宗结点find[b]:b的祖宗结点
else //也可以是op[0] //让a的祖宗结点的父节点指向b的祖宗结点
{ //就是把a,b合并
if (find(a) == find(b))
puts("Yes");//如果a,b的祖宗结点一样,证明a,b在一个集合中
else puts("No");
}
}
return 0;
}
p[find(a)] = find(b)解释
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int p[N], cnt[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;
cnt[i] = 1;
}
while (m -- )
{
string op;
int a, b;
cin >> op;
if (op == "C")
{
cin >> a >> b;
a = find(a), b = find(b);
if (a != b)
{
p[a] = b;
cnt[b] += cnt[a];
}
}
else if (op == "Q1")
{
cin >> a >> b;
if (find(a) == find(b)) puts("Yes");
else puts("No");
}
else
{
cin >> a;
cout << cnt[find(a)] << endl;
}
}
return 0;
}
🏳️🌈🏳️🌈🏳️🌈🏳️🌈🏳️🌈🏳️🌈
我们只需要遍历一下点的集合,如果两个点的横坐标或者众坐标相等,那么我们就把这两个点放入一个集合中
最后我们只需要统计一下有几个集合就知道解了,解的个数就是集合的个数减一,我们可以这么想如果有两个不相交的集合,我们只需要加一个点就可以让两个集合联系起来
#include <iostream>
using namespace std;
const int N= 1e5 + 10;
struct node
{
int xi, yi;
} w[N];
int p[N];
int find(int x) //路径压缩
{
if (p[x]!=x) p[x]=find(p[x]);
return p[x];
}
void merge(int x, int y)
{
int a = find(x);
int b = find(y);
if (a != b)
p[a] = b;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) p[i] = i;//初始化
for (int i = 1; i <= n; i++)
scanf("%d%d", &w[i].xi, &w[i].yi);
for (int i = 1; i < n; i++) //防止越界,i要小于n不能等
{
for (int j = i + 1; j <= n; j++)
{
if (w[i].xi == w[j].xi || w[i].yi == w[j].yi)//横坐标相等||纵坐标相等
merge(i, j);//合并为一个联通块
//注意:这里合并的是i,j 不是w[i]w[j]
//因为w[i]w[j]仅仅是判断横坐标纵坐标是否相等
//⭐⭐⭐i,j来组成联通块⭐⭐⭐
//if(find(i)!=find(j))
//p[find(i)]=find(j);
}
}
//分散的点连成联通块后,判断有多少个联通块
int ans = 0;
for (int i = 1; i <= n; ++i)
if (p[i] == i)
ans++;
printf("%d\n", ans - 1);
}
Code over!
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之家整理,本文链接:https://www.bmabk.com/index.php/post/131353.html