合并集合
这个数据结构适合做的事
10余年的新干网站建设经验，针对设计、前端、开发、售后、文案、推广等六对一服务，响应快，48小时及时工作处理。
成都全网营销的优势是能够根据用户设备显示端的尺寸不同，自动调整新干建站的显示方式，使网站能够适用不同显示终端，在浏览器中调整网站的宽度，无论在任何一种浏览器上浏览网站，都能展现优雅布局与设计，从而大程度地提升浏览体验。
创新互联建站从事“
新干网站设计”,“
新干网站推广”以来，每个客户项目都认真落实执行。
树根是集合的标志点，用来识别不同的集合（不一定要写成二叉树）
基本原理：每个集合用一棵树来表示，树根的编号就是整个集合的编号。每个结点存储他的父节点，p[x]表示x的父节点
优化：路径压缩
从x往上找找到根节点之后，将经过的路径上的结点的指向全部直接改成找到的根节点
还有一个优化叫做按值优化，有兴趣自己搜，用处不大
#include#include
#include#include#includeusing namespace std;
const int N = 100010;
int n, m;
int p[N];
int find(int x) //返回x的父亲节点，并且实现压缩路径优化
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >>n >>m;
char op;
int a, b;
for (int i = 0; i< n; i++) p[i] = i;
while (m--)
{
cin >>op >>a >>b;
if (op == 'M') p[find(a)] = find(b);
else if (op == 'Q')
if (find(a) == find(b)) cout<< "Yes"<< endl;
else cout<< "No"<< endl;
}
return 0;
}
连通块中点的数量
#include#include
#include#include#includeusing namespace std;
const int N = 100010;
int m, n;
int p[N], siz[N];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
char op[2];
cin >>n >>m;
int a, b;
for (int i = 1; i<= n; i++)
{
p[i] = i;
siz[i] = 1;
}
while (m--)
{
cin >>op;
if (op[0] == 'C')
{
cin >>a >>b;
if (find(a)!= find(b))
{
siz[find(b)] += siz[find(a)];
p[find(a)] = find(b);
}
}
else if (op[0] == 'Q')
{
if (op[1] == '1')
{
cin >>a >>b;
if (find(a) == find(b))
cout<< "Yes"<< endl;
else
cout<< "No"<< endl;
}
else
{
cin >>a;
cout<< siz[find(a)]<
这里需要特别判断一下，要不就会重复加
食物链
#include#include
using namespace std;
const int N = 100010;
int n,m;
int p[N],d[N];
int find(int x)
{
if(p[x] != x)
{
int t = find(p[x]);
d[x] += d[p[x]];//
p[x] = t;//
}
return p[x];
}
int main()
{
cin>>n>>m;
for(int i = 1 ; i<= n ; i ++ ) p[i] = i;
int res = 0;
while(m--)
{
int t,x,y;
cin>>t>>x>>y;
if (x >n || y >n ) res ++;
else
{
int px = find(x);
int py = find(y);
if(t == 1)
{
if(px == py && (d[x] - d[y]) % 3 ) res++;
else if(px != py )
{
p[px] = py;
d[px] = d[y] - d[x];
}
}
else
{
if(px == py && (d[x] - d[y] - 1) % 3 ) res++;
else if(px != py )
{
p[px] = py;
d[px] = d[y] - d[x] + 1;
}
}
}
}
cout<
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
本文名称：并查集算法-创新互联
浏览路径：
http://cdkjz.cn/article/dsjopj.html
