算法基础课第二章并查集-CSDN博客

本文链接：https://blog.csdn.net/csdn_ggboy/article/details/121067282

本文详细介绍了并查集的基本概念，包括朴素并查集的查找和合并操作，以及维护集合大小和元素到祖宗节点距离的扩展版本。通过实例展示了如何在食物链问题中利用并查集来表示和管理物种关系。重点讲解了如何在不同场景下使用并查集优化问题解决。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

简单并查集

(1)朴素并查集：

    int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);


(2)维护size的并查集：

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);


(3)维护到祖宗节点距离的并查集：

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

种类并查集

权值并查集

食物链

食物链这道题是要求维护 $x$ 吃 $y$ ， $y$ 吃 $z$ ， $z$ 吃 $x$ 的关系，那么我们将并查集扩大三倍，表示三个族群,则可以得到相互的关系 $(x, y)$ 同类， $(x, y + n)$ ,x吃y, $(x + n, y + 2 n)$ ,x吃y, $(x + 2 n, y)$ x吃y

种类并查集


int f[150005];
int find(int x)
{
	if(f[x]==x)return x;
	f[x]=find(f[x]);
	return f[x];
}
void merge(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	f[fx]=fy;
}
main(void)
{
	int n,k,jia=0;
	int x,y,cmd;
	n=read();
	k=read();
	for(int i=1;i<=3*n;i++)f[i]=i;
	for(int i=1;i<=k;i++)
	{
		cmd=read();
		x=read();
		y=read();
		if(x>n||y>n)jia++;
		else if(cmd==2&&(x==y||find(x)==find(y)||find(y)==find(x+n)))jia++; //x、y是同类或者y吃x 不可以 
		else if(cmd==1&&(find(x)==find(y+n)||find(y)==find(x+n)))jia++;//x吃y或者y吃x 不可以 
		else
		{
			if(cmd==1)
			{
				merge(find(x),find(y));	
				merge(find(x+n),find(y+n));
				merge(find(x+2*n),find(y+2*n));
			}
			else
			{
				merge(find(x),find(y+n));
				merge(find(x+n),find(y+2*n));
				merge(find(x+2*n),find(y));
			}
		}
	}
	cout<<jia;
}

权值并查集


const int maxn=50010;
int f[maxn];
int rf[maxn];
//rex[x]是x与祖先f[x]的关系 
//0同类，1吃，2被吃
int find(int x)
{
	if(f[x]==x)return x;
	int t=f[x];
	f[x]=find(f[x]);
	rf[x]=(rf[x]+rf[t])%3;
	return f[x];
} 
void merge(int x,int y,int re)
{
	f[x]=y;//必须更新到祖先再使用这个函数，否则会顶掉原f[x] 
	rf[x]=re; 
}
main(void)
{
	int n,k,jia=0;
	n=read();
	k=read();
	_1for(i,n)f[i]=i;
	_1for(p,k)
	{
		int re,x,y;
		re=read();
	 	x=read();
		y=read();
		if(x>n||y>n)jia++;
		else if(re==2&&x==y)jia++;
		else if(find(x)==find(y))//已经有了关系
		{
			if(re-1!=(rf[x]-rf[y]+3)%3)jia++;//向量运算的思路 
		} 
		else
		{
			int newre=(re-1+rf[y]-rf[x]+3)%3;
			merge(find(x),find(y),newre);
		}
	}
	cout<<jia;
}