题目描述
解读yxc。
这个问题,主要搞懂以下几个问题?
- 递归的含义?
- p[N]的含义?
解答
- 类比高中学到的通项公式的求法;
- p[N],在此表示每个节点的父节点;及在进行find之后,该节点对应的祖先节点。
C++ 代码
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int p[N]; // 当前节点的父节点;
// 该函数的含义:查找a所在集合的祖先节点下标,从1开始, 并内部更新p[a]为a节点的祖先节点。
int find(int a)
{
// 根据通项公式,假设p[a]的祖先节点已知。
if (p[a] != a) p[a] = find(p[a]);
return p[a];
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
// 初始化每个集合
for (int i = 1; i <= n; i++) p[i] = i;
int a, b;
char op[2];
while (m--)
{
scanf("%s%d%d", op, &a, &b);
if (op[0] == 'M') p[find(a)] = find(b);
else {
if (find(a) == find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}
大佬,请问p[a] = find(p[a])怎么理解?
为什么不写成p[a] = find(a)?
写的很好hh