Check Whether Two People Are Blood Relatives in a Family Graph
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
A family graph records parent-child relationships between people. Write a function that decides whether two given people are blood relatives, meaning that they share at least one common ancestor.
The question resembles a common-ancestor question on a tree, but a family graph is not a tree: each person can have two recorded parents, there are many founders whose parents are unknown, and separate family lines join whenever two people from different lines have a child together.
### Function Signature
```python
def are_blood_relatives(relations: list[list[str]], a: str, b: str) -> bool:
```
### Rules
- `relations[i] = [parent, child]` records that `parent` is a parent of `child`.
- The ancestors of a person are the person themselves, their parents, their parents' parents, and so on up every recorded line.
- Return `True` if at least one person is an ancestor of both `a` and `b`, and `False` otherwise.
- Under this rule a person is related to their parents, grandparents, children, siblings, half-siblings, cousins, aunts and uncles. Two people linked only through a partner or a shared child, such as the two parents of a child who have no common ancestor themselves, are not related.
- A person who never appears as a child in `relations` has no recorded parents. `a` or `b` may not appear in `relations` at all; such a person's only ancestor is themselves.
### Constraints
- `0 <= len(relations) <= 10^5`
- Every name is a string of 1 to 20 ASCII letters or digits. Names are case-sensitive, and two different strings are two different people.
- A person appears as the child in at most two relations, no relation is listed twice, and no relation has `parent == child`.
- The relations contain no cycle: nobody is their own ancestor through one or more parent links.
- `a` and `b` follow the same name format, and `a != b`.
### Examples
**Example 1**
```text
Input: relations = [["Ann", "Cal"], ["Ben", "Cal"], ["Ann", "Dee"], ["Ben", "Dee"],
["Cal", "Eli"], ["Fay", "Eli"], ["Dee", "Gus"]]
a = "Eli", b = "Gus"
Output: True
```
Eli's ancestors are Eli, Cal, Fay, Ann and Ben; Gus's are Gus, Dee, Ann and Ben. Ann and Ben are ancestors of both, so Eli and Gus (first cousins) are related.
**Example 2**
```text
Input: relations = [["Ann", "Cal"], ["Ben", "Cal"], ["Ann", "Dee"], ["Ben", "Dee"],
["Cal", "Eli"], ["Fay", "Eli"], ["Dee", "Gus"]]
a = "Fay", b = "Cal"
Output: False
```
Fay has no recorded parents, so her only ancestor is herself; Cal's ancestors are Cal, Ann and Ben. Fay and Cal are the two parents of Eli but share no ancestor.
**Example 3**
```text
Input: relations = [["Ann", "Cal"], ["Ben", "Cal"], ["Ann", "Dee"], ["Ben", "Dee"],
["Cal", "Eli"], ["Fay", "Eli"], ["Dee", "Gus"]]
a = "Ann", b = "Gus"
Output: True
```
Ann counts as her own ancestor and is Gus's grandparent, so she is a common ancestor.
Overview: A graph coding question on a family graph given as parent-child pairs, where each person has up to two parents and there is no single root. Decide whether two people are blood relatives, meaning they share at least one common ancestor. It tests modeling a DAG, graph traversal and a precise definition of relatedness.
