# 最远祖先

1     2  3 /  \  /      \
4    5        6                   \
7 

输入是int\[]\[] input, input\[0]是input\[1] 的parent，比如 {{1,4}, {1,5}, {2,5}, {3,6}, {6,7}}会形成上面的图 

第一问是只有0个parents和只有1个parent的节点 

第二问是 两个指定的点有没有公共祖先 bfs/dfs

第三问是就一个点的最远祖先，如果有好几个就只需要输出一个就好，举个栗子，这里5的最远祖先可以是1或者2，输出任意一个就可以 bfs

```
 public int findEarliestAncestor(int[][] edges, int node)
    {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for(int i = 0; i< edges.length; i++)
        {
            int parent  = edges[i][0];
            int child = edges[i][1];
            map.putIfAbsent(child, new HashSet<Integer>());
            map.get(child).add(parent);
        }

        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> path = new HashSet<Integer>();
        queue.offer(node);
        path.add(node);

        int earliestAncestor = node;
        while(!queue.isEmpty())
        {
            int size = queue.size();
            for(int i = 0; i< size; i++)
            {
                int current = queue.poll();
                earliestAncestor = current;
                for(Integer nextElement: map.get(current))
                {
                    if(!path.contains(nextElement))
                    {
                        queue.offer(nextElement);
                        path.add(nextElement);
                    }
                }
            }
        }
        return earliestAncestor;   
    }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/wayfair/oa/karat/zui-yuan-zu-xian.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.