1.题目描述
或许你并不知道，你的某个朋友是你的亲戚。
他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。
如果能得到完整的家谱，判断两个人是否是亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。
在这种情况下，最好的帮手就是计算机。
为了将问题简化，你将得到一些亲戚关系的信息，如Marry和Tom是亲戚，Tom和Ben是亲戚，等等。
从这些信息中，你可以推出Marry和Ben是亲戚。
请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。
输入格式
输入由两部分组成。
第一部分以 N,M 开始。N 为问题涉及的人的个数。这些人的编号为 1,2,3,…,N。下面有 M 行，每行有两个数 ai,bi，表示已知 ai 和 bi是亲戚。
第二部分以 Q开始。以下 Q 行有 Q 个询问，每行为 ci,di，表示询问 ci 和 di 是否为亲戚。
第二部分以 Q开始。以下 Q 行有 Q 个询问，每行为 ci,di，表示询问 ci 和 di 是否为亲戚。
输出格式
对于每个询问 ci,di，输出一行：若 ci和 di 为亲戚，则输出“Yes”，否则输出“No”。
数据范围
1≤N≤20000
1≤M≤10的六次方
1≤Q≤10的六次方
输出样例：
YesNoYes
2.思路分析
我们先初始化p数组
然后输入m个数
我们查询一下，如果root1(find(a),即a的根节点)不是root2(find(b),即b的根节点)，我们就把它们连接起来
最后输入q个数判断一下就行了，如果它们都是一个祖宗，我们就输出Yes，反之输出No
注意用BufferedReader和BufferedWriter优化一下输入输出，不然会超时
关于快速输入可以看一下我的这篇博客
https://blog.csdn.net/m0_68055637/article/details/128551437
3.Ac代码
import java.io.*; public class Main { static int N=20010; static int []p=new int[N]; //存储每个点的祖宗节点 public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); String []s=br.readLine().split(" "); int n=Integer.parseInt(s[0]),m=Integer.parseInt(s[1]); for (int i = 0; i < n; i++) { p[i]=i; } while (m-->0){ s=br.readLine().split(" "); int a=Integer.parseInt(s[0]),b=Integer.parseInt(s[1]); int root1=find(a),root2=find(b); //分别找到两个人的祖宗节点，并判断是不是亲戚 if(root1!=root2) p[root1]=root2; //如果不是，添加至同族 } int t=Integer.parseInt(br.readLine()); while (t-->0){ s=br.readLine().split(" "); int a=Integer.parseInt(s[0]),b=Integer.parseInt(s[1]); bw.write(find(a)==find(b)?"Yes":"No"); bw.newLine(); //换行 } bw.flush(); //输出缓冲区才能输出 } private static int find(int x) { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } }
感谢你能看完， 如有错误欢迎评论指正，有好的思路可以交流一波，如果对你有帮助的话，点个赞支持下
