并查集算法-创新互联

这个数据结构适合做的事

树根是集合的标志点，用来识别不同的集合（不一定要写成二叉树）

基本原理：每个集合用一棵树来表示，树根的编号就是整个集合的编号。每个结点存储他的父节点，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<