[蓝桥学习] 并查集

并查集基础

并查集用来存储图中结点的连通关系。

一个点的根结点是该点的父亲的父亲的...父亲，根：某个结点的父亲是自己

当两个点的根相同时，就说他们是同一类的，连通的

找根

但是，如果点特别多且形成链的话，找根就会效率很低，所以，可以一边找根，一边把该结点的父结点直接设为根（路径压缩）

合并

#include <iostream>
using namespace std;

const int N = 2e5 + 5;
int n,m;
int pre[N];

int root(int x)
{
  return pre[x] = pre[x]==x?x:root(pre[x]);
}


int main()
{
  // 请在此输入您的代码
  cin >> n >> m;
  //并查集初始化，各个点独立
  for(int i = 1 ; i <= n ; i++) pre[i]=i; 
  while(m--)
  {
    int op,x,y;
    cin >> op >> x >> y;
    if(op == 1)
    {
      //合并操作
      pre[root(x)] = root(y);
    }
    else
    {
      if(root(x)==root(y)) cout << "YES" << '\n';
      else cout << "NO" << '\n';
    }
  }
  
  return 0;
}

带权并查集

不仅维护集合关系，为每个集合赋予权值，并在路径上表示出来，大小、重要性

dis[x] += dis[f[x]] 一定得在find(f[x]) 后面，这样才能从离根近的累计算到离根远的。