解决的问题

1. 查找图是否成环
2. 查询数据是否在同一个连通图中

思想

利用数组建树，数组元素值代表该位置的父亲结点，如果为数组元素值为本身代表为独立结点

找祖先

每次询问自己的父亲，直到查找到数组元素值为本身的点即为祖先。

合并两个圈

合并两圈=把a2图的头结点的父亲结点改为a1图的头结点

成环的标志是：圈内某两元素之间还有一条边
也就是： 当发现某条边的两个结点的根节点是同一结点时，代表着成环了

压缩路径

可能会出先这种情况，复杂度变为O（n）

因此需要优化：压缩路径
直接把在路径上的每个节点都直接连接到根上

模板代码

模板题目

#include
using namespace std;
const int N=1e5+10;
int fa[N];//father

void init(int n){
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
}

int getfa(int x){
    if(fa[x]!=x) fa[x]=getfa(fa[x]);
    return fa[x];
}
void join(int x,int y){
    x=getfa(x);
    y=getfa(y);
    if(x!=y)fa[x]=y;
}

int main()
{

    int n,m;
    cin>>n>>m;
    init(n);
    while(m--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        if(x==1)
        {
            join(y,z);
        }
        else
        {
            if(getfa(y)==getfa(z)) cout<<"Y"<

//记录并初始化子树的大小为 1
void Join(int x, int y)
{
  x=find(x), y=find(y);
  if (x==y) return;
  if (size[x] > size[y])  // 保证小的合到大的里
    swap(x, y);
  fa[x] = y;
  size[y] += size[x];
}//按大小合并

//记录并初始化子树的深度为 1
int depth[maxn];// 深度
void Join(int x, int y)
{
  x=find(x),y=find(y);
  if (x==y) return;
  if(depth[x]depth[y])fa[y]=x;
  if(depth[x]==depth[y])
  {
      depth[y]++;
      fa[x]=y;
   }// 深度小的合并到深度大的集合里
/*
    因为将压缩了路径，也就是说直接将数据连接到根节点；
    也就是说如果两个高度不一样的并查集合并，深度不会变化，就是最深的树的深度。
*/
}