https://www.zhihu.com/question/46440863?sort=created
https://blog.csdn.net/qq_41955236/article/details/98472911
https://www.luogu.com.cn/problem/P2597

import java.util.*;

public class DagLCA {

    int nodeCnt;
    int[] topSort;
    int[] inDegrees;
    int[][] st; // 父节点跳表
    Map<Integer, GraphNode> nodeMap;
    List<Integer> roots;

    Map<Integer, GraphNode> dominatorTree;
    int[] parent; // 支配树上的父节点
    int[] depths; // 支配树上的深度
    private static final int ABSOLUTE_ROOT_ID = 0;
    private int dominatorTreeRootId;


    public DagLCA(int[][] edges, int nodeCnt) {
        this.nodeCnt = nodeCnt;
        topSort = new int[nodeCnt + 1];
        inDegrees = new int[nodeCnt + 1];
        parent = new int[nodeCnt + 1];
        depths = new int[nodeCnt + 1];
        nodeMap = new HashMap<>();
        dominatorTree = new HashMap<>();
        st = new int[nodeCnt + 1][nodeCnt];
        Arrays.fill(parent, -1);
        parent[0] = 0;
        for (int[] edge : edges) {
            inDegrees[edge[1]]++;
            addEdge(edge[0], edge[1], nodeMap);
        }
        topologySort();
        System.out.println(dominatorTree);
    }

    private void addEdge(int from, int to, Map<Integer, GraphNode> graph) {
        GraphNode fromNode = initOrGetGraphNode(from, graph);
        GraphNode toNode = initOrGetGraphNode(to, graph);
        fromNode.next.add(to);
        toNode.pre.add(from);
    }

    private GraphNode initOrGetGraphNode(int id, Map<Integer, GraphNode> graph) {
        GraphNode node;
        if (!graph.containsKey(id)) {
            node = new GraphNode(id);
            graph.put(id, node);
        }
        return graph.get(id);
    }

    private void topologySort() {
        roots = getDAGGraphRoot();
        Deque<Integer> nextUpdateNodes = new LinkedList<>();

        if (roots.size() > 1) {
            addAbsoluteRoot();
            dominatorTreeRootId = ABSOLUTE_ROOT_ID;
            nextUpdateNodes.add(ABSOLUTE_ROOT_ID);
        } else {
            dominatorTreeRootId = roots.get(0);
            parent[dominatorTreeRootId] = dominatorTreeRootId;
            st[dominatorTreeRootId][0] = dominatorTreeRootId;
            nextUpdateNodes.addAll(roots);
        }

        while (!nextUpdateNodes.isEmpty()) {
            int nodeId = nextUpdateNodes.pop();
            GraphNode DAGNode = nodeMap.get(nodeId);

            // 连接自身和父节点，当走到这一步时，parent数组一定已经完成更新
            if (nodeId != dominatorTreeRootId) {
                addEdge(parent[nodeId], nodeId, dominatorTree);
                st[nodeId][0] = parent[nodeId];
                depths[nodeId] = depths[parent[nodeId]] + 1;
            }

            // 更新父节点跳表
            for (int i = 1; i < nodeCnt; i++)
                st[nodeId][i] = st[st[nodeId][i - 1]][i - 1];

            // 遍历子节点，更新入度并求前驱LCA
            for (int child : DAGNode.next) {
                // 如果子节点前驱只有一个则被唯一前驱支配，
                // 如果有多个则被所有前驱的最近公共父节点支配。
                if (nodeMap.get(child).pre.size() == 1) {
                    parent[child] = nodeId;
                } else if (parent[child] != -1) {
                    parent[child] = lca(parent[child], nodeId);
                } else if (parent[child] == -1) {
                    parent[child] = nodeId;
                }
                // 子节点入度减1
                inDegrees[child]--;
                // 入度为0的节点入队
                if (inDegrees[child] == 0) nextUpdateNodes.add(child);
            }

        }
    }

    private List<Integer> getDAGGraphRoot() {
        List<Integer> graphRootNodes = new ArrayList<>();
        for (int i = 1; i < inDegrees.length; i++) {
            if (inDegrees[i] == 0) graphRootNodes.add(i);
        }
        return graphRootNodes;
    }

    // 如果同时有多个起点，需要为整个图配置一个唯一的根节点。
    private void addAbsoluteRoot() {
        initOrGetGraphNode(0, nodeMap);
        initOrGetGraphNode(0, dominatorTree);
        for (int rootId : roots) {
            parent[rootId] = ABSOLUTE_ROOT_ID;
            addEdge(0, rootId, dominatorTree);
            addEdge(0, rootId, nodeMap);
            depths[rootId]++;
            inDegrees[rootId]++;
        }
    }

    public int lca(int x, int y) {
        if (x == y) return x;
        if (depths[x] < depths[y]) {
            int tmp = x;
            x = y;
            y = tmp;
        }
        for (int i = nodeCnt - 1; i >= 0; i--)
            if (depths[st[x][i]] >= depths[y])
                x = st[x][i];
        if (x == y) return x;
        for (int i = nodeCnt - 1; i >= 0; i--) {
            if (st[x][i] != st[y][i]) {
                x = st[x][i];
                y = st[y][i];
            }
        }
        return st[x][0];
    }


    public static void main(String[] args) {
        int[][] edges = new int[][]{{1, 3}, {1, 4}, {2, 4}, {2, 5}, {3, 6}, {4, 6}, {5, 6}, {5, 7}, {6, 8}, {6, 9}, {8, 11}, {8, 10}, {9, 10}, {9, 12}, {7, 13}, {13, 14}, {14,15}};
        DagLCA lca = new DagLCA(edges, 15);
        System.out.println(lca.lca(10, 11));
    }

}