# Find child having n parent ( Graph Problem )

Question:
Suppose we have some input data describing a graph of relationships between parents and children over multiple generations. The data is formatted as a list of (parent, child) pairs, where each individual is assigned a unique integer identifier.

Write a method that takes a list of parent – child tuples and x number. It returns all the nodes having a parent count equals to x.

Input                : [ [1, 3], [2, 3], [3, 6], [5, 6], [5, 7], [4, 5], [4, 8], [8, 9]] and 0
Sample output : 1, 2, 4

Input                : [ [1, 3], [2, 3], [3, 6], [5, 6], [5, 7], [4, 5], [4, 8], [8, 9]] and 1
Sample output : 8, 7, 9

Input                : [ [1, 3], [2, 3], [3, 6], [5, 6], [5, 7], [4, 5], [4, 8], [8, 9]] and 2
Sample output : 3, 5, 6

Solution:
Key to solving this question is to come up with a (N+1) x N matrix. N is the number of nodes. An extra row is to store the sum of the column. The column of this matrix represents the child node and row represents parent nodes. For each input pair value, you can mark 1 at relevant position in a matrix. For example, [1, 3]  suggest matrix[1][3] =1. So, each 1 in the matrix represents parent to child connection. Once you form this. It is very easy to derive the parent count. Each column sum is the total number of parents pointing to that child.

For this solution, have considered -1 as the parent value for the root nodes. So, if you have a root node, it will have a parent value as -1 and that is the reason you will see -1 check in the code.

Code:

Git Url: FindChildren.java

Complexity: O( n * n ). As we need to traverse entire matrix for the column sum.