18.8 Java slightly better solution

#1

We can maintain each vertex’s maxDistance inside DFS itself. The process of DFS on the DAG has already implicitly maintained topological order. We don’t need to explicitly build a Deque.

public static int maxLevel = 0;

public static class GraphVertex {

    public List<GraphVertex> edges = new ArrayList<>();
    // Set maxDistance = 0 to indicate unvisited vertex.
    public int maxDistance = 0;
}

public static int findLargestNumberTeams(List<GraphVertex> G) {
    for (GraphVertex g : G) {
        if (g.maxDistance == 0) {
            DFS(g);
        }
    }
    return maxLevel;
}

private static int DFS(GraphVertex curr) {
    curr.maxDistance = 1;
    for (GraphVertex vertex : curr.edges) {
        curr.maxDistance = Math.max(curr.maxDistance, (vertex.maxDistance == 0 ? DFS(vertex) : vertex.maxDistance) + 1);
    }

    maxLevel = Math.max(maxLevel, curr.maxDistance);
    return curr.maxDistance;
}
0 Likes
#2

Hi @ray,

It definitely looks pretty good, and I wonder can you hide the use of maxLevel or not?

Thanks again for this update.

0 Likes