☘前言☘
今日份水题开始。希望有想要提高的同学跟我们一起来刷题0.0
4.11日每日一题——亲戚
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
⏳全文大约阅读时间： 20min
全文目录
☘前言☘
解题思路
📑写在最后
P1551 亲戚
解题思路
挺好的题目，本来没看过并查集的概念，这次了解了一下，其实思路就是每个节点都保存自己的最祖先的那个，如果最终两个祖先相同就直接返回Yes，否则就是No，然后其实每个节点保存自己的最祖先的那个节点信息就好了，所以在查找祖先的时候可以把数组中的元素直接标记加速。
#include <stdio.h> int f[5010]; int Find(int x){ if(f[x] == x) return x; else return f[x] = Find(f[x]); } int main(){ int m,n,k; scanf("%d %d %d",&m,&n,&k); for(int i = 1;i<= m;++i) f[i] = i; //指向自己 while(n--){ int o,k; scanf("%d %d",&o, &k); f[Find(o)] = Find(k);//合并两个并查集 } while(k--){ int o,k; scanf("%d %d",&o, &k); Find(o) == Find(k) ? printf("Yes\n") : printf("No\n"); } return 0; }
