Shared Ancestor of Two People
Problem statement
You are given data about parents and children over several generations. Each entry of parentChildPairs is [parent, child], and every person has a unique integer ID.
An ancestor of a person is one of their parents, a parent of one of their parents, and so on up the family. A person is not their own ancestor.
Return true if person1 and person2 have at least one ancestor in common, and false otherwise.
For example, the pairs [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[9,11],[14,4],[13,12],[12,9]] describe this family, with parents above their children:
14 13
| |
1 2 4 12
\ / / | \ /
3 5 8 9
\ / \ \
6 7 11Here 6 and 8 have the common ancestor 4.
Function
hasCommonAncestor(parentChildPairs: int[][], person1: int, person2: int) → booleanExamples
Example 1
parentChildPairs = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[9,11],[14,4],[13,12],[12,9]]person1 = 6person2 = 8return = trueThis is the family graph from the statement. The ancestors of 6 are 3, 5, 1, 2, 4 and 14. The ancestors of 8 are 4 and 14. Both lists contain 4 (and 14), so the answer is true.
Example 2
parentChildPairs = [[10,20],[10,30],[20,40],[30,40],[50,60]]person1 = 10person2 = 40return = false10 is an ancestor of 40, but that alone is not enough. 10 has no parents, so it has no ancestors at all, and the two people cannot share one. The answer is false.
Example 3
parentChildPairs = [[10,20],[10,30],[20,40],[30,40],[50,60]]person1 = 20person2 = 30return = true20 and 30 both have the parent 10, so 10 is an ancestor of both. The answer is true.
Constraints
1 <= parentChildPairs.length <= 500parentChildPairs[i].length == 21 <= parentChildPairs[i][j] <= 10^5parentChildPairs[i][0] != parentChildPairs[i][1], and no pair appears twice.- The pairs have no cycle: nobody is their own ancestor.
person1 != person2, and both appear inparentChildPairs.