教育网站设计方案,建设网站技术公司电话号码,wordpress for search,国外营销网站1.题目描述或许你并不知道#xff0c;你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱#xff0c;判断两个人是否是亲戚应该是可行的#xff0c;但如果两个人的最近公共祖先与他们相隔好几代#xff0c;使得家谱十分庞…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 是否为亲戚。输出格式对于每个询问 ci,di输出一行若 ci和 di 为亲戚则输出“Yes”否则输出“No”。数据范围1≤N≤200001≤M≤10的六次方1≤Q≤10的六次方输入样例10 72 45 71 38 91 25 62 333 47 108 9输出样例YesNoYes2.思路分析我们先初始化p数组然后输入m个数我们查询一下如果root1(find(a),即a的根节点)不是root2(find(b),即b的根节点)我们就把它们连接起来最后输入q个数判断一下就行了如果它们都是一个祖宗我们就输出Yes反之输出No注意用BufferedReader和BufferedWriter优化一下输入输出不然会超时关于快速输入可以看一下我的这篇博客https://blog.csdn.net/m0_68055637/article/details/1285514373.Ac代码import java.io.*;public class Main {static int N20010;static int []pnew int[N]; //存储每个点的祖宗节点public static void main(String[] args) throws IOException {BufferedReader brnew BufferedReader(new InputStreamReader(System.in));BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out));String []sbr.readLine().split( );int nInteger.parseInt(s[0]),mInteger.parseInt(s[1]);for (int i 0; i n; i) {p[i]i;}while (m--0){sbr.readLine().split( );int aInteger.parseInt(s[0]),bInteger.parseInt(s[1]);int root1find(a),root2find(b); //分别找到两个人的祖宗节点并判断是不是亲戚if(root1!root2) p[root1]root2; //如果不是添加至同族}int tInteger.parseInt(br.readLine());while (t--0){sbr.readLine().split( );int aInteger.parseInt(s[0]),bInteger.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];}
}
感谢你能看完 如有错误欢迎评论指正有好的思路可以交流一波如果对你有帮助的话点个赞支持下
