# Efficient algorithm to track all the direct parents and transitive parents(parents of parents and grand parents) in a directed acyclic graph

I am preparing for online coding assessment, where I have come across a question to write an algorithm to find the list of direct parents and transitive parents for each vertex in a directed acyclic graph.

Input: The first line is a number indicating how many lines follow. On each following line of input, the first item represents a module in our dependency graph, then a comma, followed by all of it's children also separated by commas. There is no circles in the dependency graph. For the example, the input looks like this:

5

A,E,N,S

S,H,N

E,N

H

N

Output

A,0(no parents)

E,1(A is direct parent)

H,2(S direct parent, A transitive parent)

N,3(A,S,E are direct parents)

S,1(A is a direct parent)

public class Solution {

public static void main(String[] args) {
List<List<Character>> list = new ArrayList<>();
Solution sol = new Solution();
sol.calculateCost(5,list);
}

public void calculateCost(int number, List<List<Character>> list){
Map<Character,Node> nodeMap = constructGraph(list);
StringBuilder sb = new StringBuilder();
for(Map.Entry<Character,Node> entry: nodeMap.entrySet()){
sb.append(entry.getKey());
sb.append(",");
sb.append(entry.getValue().allParentCount()+1);
sb.append(" ");
}
System.out.println(sb.toString().trim());
}

private Map<Character,Node> constructGraph(List<List<Character>> list){
Map<Character,Node> nodeMap = new HashMap<>();

for(List<Character> edges : list){
Character sourceVertex = edges.get(0);
Node node = new Node(sourceVertex);
nodeMap.put(sourceVertex,node);
}
for(List<Character> edges : list){
Character sourceVertex = edges.get(0);
Node parentNode = nodeMap.get(sourceVertex);
List<Character> destinationVertices = edges.subList(1,edges.size());
for(Character destinationVertex : destinationVertices){
}
}
return nodeMap;
}
}

class Node{
Character vertex;
Set<Node> parents = new HashSet<>();

Node(Character vertex){
this.vertex = vertex;
}
}
public int allParentCount(){
return allParents().size();
}
public Set<Node> allParents(){
Set<Node> allParents = new HashSet<>();