Check whether 2 nodes have any common parent(s) in a DAG graph

Question

The input is:

An int[][], each sub array contains 2 int as {parent, child}, means there is a path from parent -> child.

e.g

{ { 1, 3 }, { 2, 3 }, { 3, 6 }, { 5, 6 }, { 5, 7 }, { 4, 5 }, { 4, 8 }, { 8, 9 } };

Or as a tree structure:

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

The task is:

Ｇiving 2 value (x, y), return a boolean value, to indicate whether they have any common parent(s).

Sample input and output:

[3, 8] => false
[5, 8] => true
[6, 8] => true

My idea:

• Represent the input data as a DAG graph, in which data are stored in a Map like this Map<Integer, LinkedList<Integer>>, where key is the vertex, value is its adjacency list. And the direction in graph is reversed (compared to input data) as child -> parent, so that easy to search for parent.
• Use a function findAvailableParents(Integer vertex) to find all parents (direct and indirect) for a single vertex, and return Set<Integer>.
• Thus, only need to call findAvailableParents() once for each input vertex, then compare whether the 2 returned Sets have any intersection. Ｉf yes, then they have common parent; otherwise, they don't.

My questions are:

• The time complexity in the solution above is between O(1) ~ O(E), right? (E is edge counts in the graph)
• Is there a better solution?

Answer 1

A modified BFS might help you to solve the problem

Algorithm: checkCommonParent

def checkCommonParent(G, v1, v2):

# Create a queues for levelorder traversal
q1 = []

# Mark all the vertices as not visited
# This will be used to cover all the parts of graph
visited = [False]*(len(G.Vertices))


for v in G.Vertices:
    if visited[v] == False:
        q1.append(v)
        visited[v] = True

    # Check a connected component and see if it has both vertices exists.
    # If it exists, that means they have a common ancestor
    v1Visited = False
    v2Visited = False
    while ((len(q1) > 0) or (len(q2) > 0)):
      while len(q1) > 0:
        curVertex = q1.popleft()
        for adjV in curVertex.adjecentVertices:
        if visited[adjV] == False:
            q1.append(adjV)
            visited[adjV] = True

            if adjV == v1:
              v1Visited = True
            elif adjV == v2:
              v2Visited = True


    if v1Visited and v2Visited: 
            return True


return False

I guess the idea is clear on the modification of BFS. Hope it helps!

Answer 2

suppose you have multiple inputs, now BFS would take around O(E) time to process each input.

All inputs can be queried in O(logn) if we do some pre computation which should take about O(nlogn) time

basically you want to find what is the Least common ancestor of those nodes
this thread in topcoder discusses the logic for a tree which can be extended to a DAG
You can also refer to this question for some further ideas

If an LCA exists between 2 nodes, then they have a common parent