AcWing 836. 并查集(数组)

• 题目： https://www.acwing.com/problem/content/description/838/

先说一下本题思路

• 1.看清题目，主要有俩个操作，合并和查询 。 总体思路是找到俩个祖宗节点，并且把俩个祖宗节点相连(其实就是改p[a的祖宗]=b的祖宗 比如p[3]=4，p[3]=p[4]=4,他们的祖宗都是4，)

• 2.合并是在一个数组中，利用下标和他所指向的值，如果他所指向的值一样，那么就是一个集合。用下表来记录具体数据。

• 3.查询直接查询祖宗节点，很好理解，就是比如说查询x，他就会查询p[x]的值，如果和x不一样，会查询find[p[x]]的值,这里有点绕，x如果和p[x]的值不一样，就查询find(p[x]),一个个找，找到祖宗节点，就是x和p[x]一样的节点，原始节点。

• 主要操作就是针对于祖宗节点进行的。

• 题目难点（个人愚见）：find函数，寻找祖宗节点的过程，下标和值的用法。

#include <iostream>

using namespace std;

const int N = 100010;

int p[N];
int find(int x)   //找祖宗节点的函数
{
  if(p[x] != x) p[x] = find(p[x]);
  return p[x];
}

bool only(int a,int b)  //判断是否在一个集合
{
  return find(a)==find(b);
}


int main()
{
  int a,b;
  char str,test;
  int n,m;

  scanf("%d%d",&n,&m);
  scanf("%c",&test);  //消除回车

  for(int i = 1;i<=n; i++)
    p[i]=i;

  while(m--)
  {

    scanf("%c %d %d",&str,&a,&b);
    scanf("%c",&test);  //消除回车
    // printf("%c%d%d\n",str,a,b);
    if(str == 'M')
    {
      p[find(a)]=find(b); //合并操作，
    }
    else if(str == 'Q')
    {
      if(only(a,b)) printf("Yes\n");
      else printf("No\n");
    }

  }

  return 0;
}