功能图中两节点碰撞时间查询的最优求解方法

问题描述 #

给定一个包含N个节点（编号1~N）的图，每个节点恰好有1条指向某个节点的有向边（可指向自身）。
我们需要处理类型为A, B的查询：两个对象分别从节点A和B同时出发，每秒沿边移动1跳，求二者碰撞所需的时间。若不可能碰撞则返回-1。
时间规则：从X移动到Y经过1跳，耗时1秒。

约束条件 #

N, Q <= 10^5（节点数、查询数）

示例 #

给定如下图结构：

A -> B -> C -> D -> E
                  ^    |
                  K <- F

• 查询(A, E)：返回3秒，因为t=3秒时二者都位于节点D。
• 查询(C, D)：返回-1秒，因为二者永远不会碰撞。

求解每个查询的最优方法是什么？

解法效率对比 #

• 暴力解法时间复杂度：O(Q * N)，无法满足1e5级别的数据规模要求
• 使用*二进制倍增（binary lifting）*技术的优化解法：预处理复杂度O(N log N)，单次查询复杂度O(log N)，整体复杂度O((N + Q) log N)，可满足数据规模要求

参考实现（Java） #

private static int[] collisionTime(int N, int Q, int[] A, int[][] queries) {
    // 祖先矩阵构建，时间复杂度 O(n * log(n))
    int M = (int) (Math.ceil(Math.log10(N) / Math.log10(2))) + 1;
    int[][] ancestor = new int[N + 1][M];
    for(int i = 1; i <= N; i++) {
        ancestor[i][0] = A[i]; // 2^0 级祖先，也就是走1步到达的节点
    }
    for(int j = 1; j < M; j++) {
        for(int i = 1; i <= N; i++) {
            ancestor[i][j] = ancestor[ancestor[i][j-1]][j-1];
        }
    }

    int[] answer = new int[Q];
    for(int i = 0; i < Q; i++) { 
        int u = queries[i][0];
        int v = queries[i][1];
        answer[i] = timeToCollide(u, v, ancestor);
    }

    return answer;
}

// 基于二进制倍增实现单次查询，时间复杂度 O(log(n))
private static int timeToCollide(int u, int v, int[][] ancestor) {
    int m = ancestor[0].length;

    // 边界情况处理
    if(u == v)                              // 初始位置已经碰撞
        return 0;              
    if(ancestor[u][m-1] != ancestor[v][m-1]) // 跳足够多次后仍不在同一节点，说明不在同一个连通分量，不可能碰撞
        return -1;

    int t = 0;
    for(int j = m - 1; j >=0; j--) {
        if(ancestor[u][j] != ancestor[v][j]) {
            u = ancestor[u][j];
            v = ancestor[v][j];
            t += 1 << j; // 等价于2^j，比Math.pow性能更优
        }
    }
    return t + 1;
}

内容的提问来源于stack exchange，提问作者tusharRawat