CareerCup

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 positive integer identifier.
<p>
For example, in this diagram, 3 is a child of 1 and 2, and 5 is a child of 4:
<p>
1 2 4 15
\ / / | \ /
3 5 8 9
\ / \ \
6 7 11
<p>
<p>
Sample input/output (pseudodata):
<p>
parentChildPairs = [
(1, 3), (2, 3), (3, 6), (5, 6), (15, 9),
(5, 7), (4, 5), (4, 8), (4, 9), (9, 11)
]
<p>
<p>
Write a function that takes this data as input and returns two collections: one containing all individuals with zero known parents, and one containing all individuals with exactly one known parent.
<p>
<p>
Output may be in any order:
<p>
findNodesWithZeroAndOneParents(parentChildPairs) => [
[1, 2, 4, 15], // Individuals with zero parents
[5, 7, 8, 11] // Individuals with exactly one parent
]
<p>
n: number of pairs in the input

public static void main(String[] argv) {
        int[][] parentChildPairs = new int[][]{
                {1, 3},
                {2, 3},
                {3, 6},
                {5, 6},
                {15, 9},
                {5, 7},
                {4, 5},
                {4, 8},
                {4, 9},
                {9, 11}};
        findNodesWithZeroAndOneParents(parentChildPairs);
    }

    public static void findNodesWithZeroAndOneParents(int[][] parentChildPairs) {
        Map<Integer, List<Integer>> childAncestor = new HashMap<>();
        for (int[] parentChildPair : parentChildPairs) {
            int parent = parentChildPair[0];
            int child = parentChildPair[1];
            if (!childAncestor.containsKey(child)) {
                childAncestor.put(child, new ArrayList<>());
            }
            List<Integer> parentValue = childAncestor.get(child);
            parentValue.add(parent);
            childAncestor.put(child, parentValue);
        }
        System.out.println(childAncestor.toString());

        dfs(childAncestor);
    }

    private static void dfs(Map<Integer, List<Integer>> childAncestor) {
        Set<Integer> childerOneParent = new HashSet<>();
        Set<Integer> parentWithOutParent = new HashSet<>();
        for (Map.Entry<Integer, List<Integer>> parent : childAncestor.entrySet()) {
            if (parent.getValue().size() == 1) {
                childerOneParent.add(parent.getKey());
            }
            List<Integer> part = parent.getValue();
            for (Integer p : part) {
                if (!childAncestor.containsKey(p)) {
                    parentWithOutParent.add(p);
                }
            }
        }
        System.out.println(childerOneParent.toString() + " / " + parentWithOutParent.toString());
    }
}