并查集算法-创新互联-成都创新互联网站建设

关于创新互联

多方位宣传企业产品与服务 突出企业形象

公司简介 公司的服务 荣誉资质 新闻动态 联系我们

并查集算法-创新互联

合并集合

这个数据结构适合做的事

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://kswsj.cn/article/dsjopj.html