第八章 不相交集类（并查集）

完整代码

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>
using namespace std;
class DisjSets
{
public:
	explicit DisjSets(int numElements);

	int find(int x) const;
	int find(int x);
	void unionSets(int root1, int root2);

private:
	vector<int> s;
};
DisjSets::DisjSets(int numElements)
	:s{ numElements,-1 }
{
	//构造函数把所有的元素均设置为-1
	//-1表示x下标对应的节点为根节点且高度为1
}
/*
* 利用路径压缩执行一次find
* 为简单起见，忽略差错检验
* 返回包含x的集合
*/
int DisjSets::find(int x)
{
	if (s[x] < 0)
	{
		return x;
	}
	else
	{
		return s[x] = find(s[x]);//把x的父节点刷新为根节点
	}
}
/*
* 合并两个不相交集类
* 为简单起见，假设root1和root2是互异的
* 并且均代表集合的名字
* root1和root2分别是set1和set2的根
*/
//按高度求并的代码
void DisjSets::unionSets(int root1, int root2)
{
	//根节点表示的元素值为负数，且绝对值为它的高度
	if (s[root2] < s[root1])//root2更深
		s[root1] = root2;//使root2成为新的根
	else
	{
		if (s[root1] == s[root2])
			--s[root1];//如果相同，则更新高度
		s[root2] = root1;
	}
}

函数

DisjSets

DisjSets::DisjSets(int numElements)
	:s{ numElements,-1 }
{
	//构造函数把所有的元素均设置为-1
	//-1表示x下标对应的节点为根节点且高度为1
}

find

/*
* 利用路径压缩执行一次find
* 为简单起见，忽略差错检验
* 返回包含x的集合
*/
int DisjSets::find(int x)
{
	if (s[x] < 0)
	{
		return x;
	}
	else
	{
		return s[x] = find(s[x]);//把x的父节点刷新为根节点
	}
}

unionSets

/*
* 合并两个不相交集类
* 为简单起见，假设root1和root2是互异的
* 并且均代表集合的名字
* root1和root2分别是set1和set2的根
*/
//按高度求并的代码
void DisjSets::unionSets(int root1, int root2)
{
	//根节点表示的元素值为负数，且绝对值为它的高度
	if (s[root2] < s[root1])//root2更深
		s[root1] = root2;//使root2成为新的根
	else
	{
		if (s[root1] == s[root2])
			--s[root1];//如果相同，则更新高度
		s[root2] = root1;
	}
}

简单模板

#include<iostream>
using namespace std;

const int N=1e5+10;
int p[N];

int find(int a)
{
    if(p[a]!=a)p[a]=find(p[a]);
    return p[a];
}
int main()
{
    int n,m;
    cin>>n>>m;
    char c;
    for(int i=1;i<=n;i++)p[i]=i;
    while(m--)
    {
        cin>>c;
        int a,b;
        cin>>a>>b;
        if(c=='M')
        {
            p[find(a)]=find(b);
        }
        else if(c=='Q')
        {
            if(find(a)==find(b))cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}