Max depth of tree when all parent pointers are provided
You shouldn't name your classes which form the data structure you operate on according to the problem you are trying to solve. The classes should be named according to their function in the data structure. Thus NodeMaxDepth should be simply Node. This also removes visual clutter when reading the code as the name is shorter yet conveys the same meaning.
I'm not 100% sure why you build the list of children for each node in a separate data structure - it seems that this should be part of the NodeMaxDepth class. It would also make for a slightly cleaner implementation of building of the children lists as each node only has to add itself to the children collection of its parent.

Something along these lines:

class Node {

    private final Node parent;
    private List&lt;Node&gt; children;

    public Node(Node parent) {
        this.parent = parent;
        children = new List&lt;Node&gt;();
    }

    public Node getParent() {
        return parent;
    }

    public void addChild(Node child) {
        children.add(child);
    }
}


public static int maxDepth(List&lt;Node&gt; nodes) {
    if (nodes.size() == 0) { throw new IllegalArgumentException("List of nodes is empty."); }

    Node root = null;

    for (Node node : nodes) {
        if (node.getParent() == null) {
            if (root != null) {
                throw new IllegalArgumentException("Tree must not have multiple roots");
            }
            root = node; 
        }
        else {
            node.getParent().addChild(node);
        }
    }

    if (root == null) {
        throw new IllegalArgumentException("This does not seem to be a tree");
    }

    return height (root);
}

If you want to optimize for memory usage and code size you could resort to a simpler algorithm by simply walking up the tree from each node to the root and remember the longest path. Worst case this would result in O(n^2) runtime if I'm not mistaken but would not require any additional memory for building the children lists. The code would also be much simpler.

As indicated by @200_success you could sacrifice a little bit more memory and find all leave nodes and just walk up from them:

// assume all nodes are leaves
HashSet&lt;Node&gt; leaves = new HashSet&lt;Node&gt;(nodes);

Node root = null;

// remove all parents as they are not leaves
for (Node node : nodes) {
    if (node.getParent() == null) { 
        root = node;
    }
    else {
        leaves.remove(node.getParent());
    }
}

if (root == null) {
    throw new IllegalArgumentException("The tree must have a root");
}

int maxHeight = 0;

for (Node leaf : leaves) {
    int height = 1;
    Node current = leaf;
    while (current.getParent() != null) {
        current = current.getParent();
        height += 1;
    }
    if (maxHeight &lt; height) {
        maxHeight = height;
    }
}

return maxHeight;

You don't really check for cycles - just that your tree has a root (you could have a normal tree and a disconnected cycle in the list).