Max DAG Edges

JavaView on GFG

Time: O(V+E)

Space: O(V)

Intuition

Maximum edges that can be added to a DAG without creating a cycle. Count edges in complete DAG minus existing.

Algorithm

1Complete DAG on n nodes has n*(n-1)/2 edges. Subtract existing edges count.

Common Pitfalls

•In a DAG with n nodes, maximum edges = n*(n-1)/2 (one direction for each pair). Just subtract current edge count.

Max DAG Edges.java

Java

// Approach: Topological order. Maximize edges from DAG structure; count based on topological positions.
// Time: O(V+E) Space: O(V)
class Solution {
    public int maxEdgesToAdd(int V, int[][] edges) {
        int E = edges.length;
        int maxPossible = ((V * (V - 1)) / 2);
        return maxPossible - E;
    }
}

Was this solution helpful?