Be the first user to complete this post

  • 0
Add to List
Beginner

417. Maximum number edges to make Acyclic Undirected/Directed Graph

Given- Given V vertices, what is the maximum number of edges can be added to make Acyclic Undirected Graph. Follow up - what is the maximum number of edges that can be added to make Acyclic Directed Graph.

Example: 

Approach:

For Undirected Graph - It will be a spanning tree (read about spanning tree) where all the nodes are connected with no cycles and adding one more edge will form a cycle. In the spanning tree, there are V-1 edges. 

For Directed Graph - Construct the graph similar to topological order  (Read about topological order - where all the edges go to one direction and there will not be any circular dependency, means there is no cycle). Take the first vertex and have a directed edge to all the other vertices, so V-1 edges, second vertex to have a directed edge to rest of the vertices so V-2 edges, third vertex to have a directed edge to rest of the vertices so V-3 edges, and so on. This will construct a graph where all the edges in one direction and adding one more edge will produce a cycle. 

So the total number of edges = (V-1) + (V-2) + (V-3) +---------+2+1 = V(V-1)/2. (sum of first N natural numbers is N(N+1)/2)

Output:

Maximum edges to make Acyclic Undirected Graph with 3 vertices are: 2
Maximum edges to make Acyclic Directed Graph with 3 vertices are: 3
---------------------------------
Maximum edges to make Acyclic Undirected Graph with 4 vertices are: 3
Maximum edges to make Acyclic Directed Graph with 4 vertices are: 6
---------------------------------
Maximum edges to make Acyclic Undirected Graph with 5 vertices are: 4
Maximum edges to make Acyclic Directed Graph with 5 vertices are: 10