Given the number of vertices N of a graph. The task is to determine the Edge cover.
Edge Cover: Minimum number of edges required to cover all vertex is known as Edge Cover.
Examples:
Input : N = 5 Output : 3 Input : N = 4 Output : 2
Example 1: For N = 5 vertices,
Edge Cover is: 3 (Choosing the edges marked in Red, all of the vertices will get covered)
Example 2: For N = 8 vertices,
Edge Cover is: 4 (Choosing the edges marked in Red, all of the vertices will get covered)
Formula:
Edge Cover = ceil (no. of vertices / 2)
Implementation:
C++
// C++ program to find Edge Cover#include <bits/stdc++.h>using namespace std;// Function that calculates Edge Coverint edgeCover(int n){ float result = 0; result = ceil(n / 2.0); return result;}// Driver Codeint main(){ int n = 5; cout << edgeCover(n); return 0;} |
Java
// Java program to find Edge Coverimport java.util.*;import java.lang.*;import java.io.*;class GFG{// Function that calculates Edge Coverstatic int edgeCover(int n){ int result = 0; result = (int)Math.ceil((double)n / 2.0); return result;} // Driver Codepublic static void main(String args[]){ int n = 5; System.out.print(edgeCover(n));}} |
Python3
# Python 3 implementation of the above approach.import math# Function that calculates Edge Cover def edgeCover(n): result = 0 result = math.ceil(n / 2.0) return result # Driver code if __name__ == "__main__" : n = 5 print(int(edgeCover(n)))# this code is contributed by Naman_Garg |
C#
// C# program to find Edge Coverusing System;class GFG{// Function that calculates Edge Coverstatic int edgeCover(int n){ int result = 0; result = (int)Math.Ceiling((double)n / 2.0); return result;}// Driver Codestatic public void Main (){ int n = 5; Console.Write(edgeCover(n));}}// This code is contributed by Raj |
PHP
<?php// PHP program to find Edge Cover// Function that calculates// Edge Coverfunction edgeCover($n){ $result = 0; $result = ceil($n / 2.0); return $result;}// Driver Code$n = 5;echo edgeCover($n);// This code is contributed by Raj?> |
Javascript
<script>// javascript program to find Edge Cover// Function that calculates Edge Cover function edgeCover(n) { var result = 0; result = parseInt( Math.ceil(n / 2.0)); return result; } // Driver Code var n = 5; document.write(edgeCover(n));// This code contributed by gauravrajput1</script> |
Output
3
Time Complexity: O(1), As we are doing constant time operations only.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
