首页 > 代码库 > 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-----------关于公共祖先的问题