题目解析
这道题主要弄懂两个问题就可以了
1:递归的含义
2:p[N]的含义
解答
-
递归的含义就相当于你问你爸爸你的祖先是谁,你爸爸也不知道,爸爸就去问爷爷,然后你的爷爷也不知道,爷爷就去问你的太爷爷,你的太爷爷年纪太大了,啥也不记得,就去问你的祖先
这个时候注意,你的祖先是知道自己是谁的,所以x ==p[x]
然后你的祖先告诉你的太爷爷我是谁,你的太爷爷告诉你的爷爷你的祖先是谁,你的爷爷告诉你的爸爸你的祖先是谁,你的爸爸在告诉你,这个时候你就知道了,这就是递归的概念
(为什么你的祖先不直接告诉你呢,因为有代沟,不想理你)注意,这个时候你,你的爸爸,你的爷爷,你的太爷爷,都知道了你的祖先是谁了,这就是路径压缩的概念
-
p[x]中储存的是每个节点的父节点,一开始并不是树状的,而是一个个单独的节点,每个节点都是根节点,都有集合编号,然后通过不断的合并才形成的树状结构
代码
import java.util.Scanner;
public class Main{
static int N = 100010;
static int[] p = new int[N];
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
for(int i = 1; i <= n; i ++) p[i] = i;
while(m-- > 0)
{
String str = in.next();
int a = in.nextInt();
int b = in.nextInt();
if(str.equals("M")) p[find(a)] = find(b); //a的祖宗节点的父亲等于b的祖宗节点,相当于两个集合合并了
else
{
if(find(a) == find(b)) System.out.println("Yes");
else System.out.println("No");
}
}
}
private static int find(int x){
if(x != p[x]) p[x] = find(p[x]); //如果当前节点不等于父节点的话,说明不是根节点,那就让父节点=根节点
return p[x];
}
}
## 通俗易懂 感谢博主
### nb
HHHHH,有意思
nb
nb
p的话理解为指针更好我感觉 一上来是自旋
6
真滴c
易懂
写的非常通俗易懂
nb