首页 > 代码库 > poj1330-----------关于公共祖先的问题
poj1330-----------关于公共祖先的问题
关于公共祖先的问题分类:
这类问题有多种解法和类型,根据题目给出的信息去判断使用哪一种
1、给你树,只支持从父亲找儿子,不支持儿子找父亲,最后要求最近公共祖先,使用dfs或者分治
2、支持儿子找父亲,求最近公共祖先,逆序,从儿子找到底,然后比较(具体看本题代码,说不清)
3、不给树,求是否有共同祖先,并查集
4、还有离线、倍增等方法、
本题属于第二种:
1、从儿子找到底,把两条路径都记录下来
2、从后往前比对两条路径,从那里开始不一样,前一个就是最近的公共祖先
3、注意需要把自己也放进路径中,因为自己可能已经是别人的父亲了
4、使用map存放儿子-》父亲的关系比较好用,因为一个孩子只能有一个父亲。
代码如下:
import java.util.HashMap;import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); int testCase = cin.nextInt(); for (int i = 0; i < testCase; i++){ int n = cin.nextInt(); HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); for (int j = 0; j < n-1; j++){ int parent = cin.nextInt(); int child = cin.nextInt(); map.put(child,parent); } int nodeOne = cin.nextInt(); int nodeTwo = cin.nextInt(); System.out.println(nca(nodeOne, nodeTwo, map, n)); } } private static int nca(int nodeOne, int nodeTwo, HashMap<Integer,Integer> map, int maxLength){ int[] nodeOneArray = new int[maxLength]; nodeOneArray[0] = nodeOne; int nodeOneIndex = 1; while (map.containsKey(nodeOne)){ nodeOneArray[nodeOneIndex] = map.get(nodeOne); nodeOne = nodeOneArray[nodeOneIndex]; nodeOneIndex++; } int[] nodeTwoArray = new int[maxLength]; nodeTwoArray[0] = nodeTwo; int nodeTwoIndex = 1; while (map.containsKey(nodeTwo)){ nodeTwoArray[nodeTwoIndex] = map.get(nodeTwo); nodeTwo = nodeTwoArray[nodeTwoIndex]; nodeTwoIndex++; } nodeOneIndex--; nodeTwoIndex--; while (nodeOneArray[nodeOneIndex] == nodeTwoArray[nodeTwoIndex]){ nodeOneIndex--; nodeTwoIndex--; if (nodeOneIndex == -1){ return nodeOneArray[nodeOneIndex+1]; } else if (nodeTwoIndex == -1){ return nodeTwoArray[nodeTwoIndex+1]; } } return nodeOneArray[nodeOneIndex+1]; }}
poj1330-----------关于公共祖先的问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。