Time for 2 nodes to collide

Question

We are given a graph of N nodes. (1-N), where each node has exactly 1 directed edge to some node (this node can be the same node).

We need to answer the queries of type : A, B, which asks time required when 2 objects collide if one start at A and other start at B. Both moves 1 hop in 1 sec. If it's not possible for them to collide time would be -1.

Time : from X -> to Y : 1 hop = 1 second.

Constraints :

N, Q <= 10^5 (number of nodes, number of queries).

Example : for given graph

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

Query(A, E) : 3 seconds, as at time t = 3 secs they both will be on node D.
Query(C, D) : -1 seconds, as they will never collide.

What's the optimal way to answer each query?

Brute Force Approach: time - O(Q * N)

Improved solution using binary lifting technique: time - O(Q * log(N))

private static int[] collisionTime(int N, int Q, int[] A, int[][] queries) {

    // ancestor matrix : creation time- 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-th ancestor. 
    }
    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;
}

// using binary lifting: time- O(log(n))
private static int timeToCollide(int u, int v, int[][] ancestor) {
    int m = ancestor[0].length;

    // edge cases
    if(u == v)                              // already in collision state
        return 0;              
    if(ancestor[u][m-1] != ancestor[v][m-1]) // their top most ancestor is not the same means they cannot collide at all.
        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 += Math.pow(2, j);
        }
    }
    return t + 1;
}

Answer 1

1. Find all the terminal cycles and designate an arbitrary vertex in each terminal cycle as the cycle root (O(N))
2. For each vertex, record the length of its terminal cycle, its distance to entry into the terminal cycle, and the distance to the terminal cycle root (O(N)).
3. Sever the outgoing link from each cycle root. This turns the graph into a forest.
4. For each query, find the closest (lowest) common ancestor of the two query nodes in this forest.
5. From the information saved about each query node and the lowest common ancestor, you can figure out the time to collision in constant time.

Step (4), the lowest common ancestor query, is a very well-studied problem. The best algorithms require only linear processing time and provide constant query time, leading to O(N + Q) time for this problem all together.