Minimum edges required to add to make Euler Circuit

0 0 9 minutes read

Given a undirected graph of n nodes and m edges. The task is to find minimum edges required to make Euler Circuit in the given graph. Examples:

Input : n = 3, 
        m = 2
        Edges[] = {{1, 2}, {2, 3}}
Output : 1

By connecting 1 to 3, we can create a Euler Circuit.

For a Euler Circuit to exist in the graph we require that every node should have even degree because then there exists an edge that can be used to exit the node after entering it. Now, there can be two cases:
1. There is one connected component in the graph In this case, if all the nodes in the graph is of even degree then we say that the graph already have a Euler Circuit and we don’t need to add any edge in it. But if there is any node with odd degree we need to add edges. There can be even number of odd degree vertices in the graph. This can be easily proved by the fact that the sum of degrees from the even degrees node and degrees from odd degrees node should match the total degrees that is always even as every edge contributes two to this sum. Now, if we pair up random odd degree nodes in the graph and add an edge between them we can make all nodes to have even degree and thus make an Euler Circuit exist.
2. There are disconnected components in the graph We first mark components as odd and even. Odd components are those which have at least one odd degree node in them. Take all the even components and select a random vertex from every component and line them up linearly. Now we add an edge between adjacent vertices. So we have connected the even components and made an equivalent odd component that has two nodes with odd degree. Now to deal with odd components i.e components with at least one odd degree node. We can connect all these odd components using edges whose number is equal to the number of disconnected components. This can be done by placing the components in the cyclic order and picking two odd degree nodes from every component and using these to connect to the components on either side. Now we have a single connected component for which we have discussed. Below is implementation of this approach:

C++

// C++ program to find minimum edge required
// to make Euler Circuit
#include <bits/stdc++.h>
using namespace std;
 
// Depth-First Search to find a connected
// component
void dfs(vector<int> g[], int vis[], int odd[],
                    int deg[],  int comp, int v)
{
    vis[v] = 1;
 
    if (deg[v]%2 == 1)
        odd[comp]++;
 
    for (int u : g[v])
        if (vis[u] == 0)
            dfs(g, vis, odd, deg, comp, u);
}
 
// Return minimum edge required to make Euler
// Circuit
int minEdge(int n, int m, int s[], int d[])
{
    // g : to store adjacency list
    //     representation of graph.
    // e : to store list of even degree vertices
    // o : to store list of odd degree vertices
    vector<int> g[n+1], e, o;
 
    int deg[n+1];  // Degrees of vertices
    int vis[n+1];  // To store visited in DFS
    int odd[n+1];  // Number of odd nodes in components
    memset(deg, 0, sizeof(deg));
    memset(vis, 0, sizeof(vis));
    memset(odd, 0, sizeof(odd));
 
    for (int i = 0; i < m; i++)
    {
        g[s[i]].push_back(d[i]);
        g[d[i]].push_back(s[i]);
        deg[s[i]]++;
        deg[d[i]]++;
    }
 
    // 'ans' is result and 'comp' is component id
    int ans = 0, comp = 0;
    for (int i = 1; i <= n; i++)
    {
        if (vis[i]==0)
        {
            comp++;
            dfs(g, vis, odd, deg, comp, i);
 
            // Checking if connected component
            // is odd.
            if (odd[comp] == 0)
                e.push_back(comp);
 
            // Checking if connected component
            // is even.
            else
                o.push_back(comp);
        }
    }
 
    // If whole graph is a single connected
    // component with even degree.
    if (o.size() == 0 && e.size() == 1)
        return 0;
 
    // If all connected component is even
    if (o.size() == 0)
        return e.size();
 
    // If graph have atleast one even connected
    // component
    if (e.size() != 0)
        ans += e.size();
 
    // For all the odd connected component.
    for (int i : o)
        ans += odd[i]/2;
 
    return ans;
}
 
// Driven Program
int main()
{
    int n = 3, m = 2;
    int source[] = { 1, 2 };
    int destination[] = { 2, 3 };
 
    cout << minEdge(n, m, source, destination) << endl;
    return 0;
}

Java

// Java program to find minimum edge
// required to make Euler Circuit
import java.io.*;
import java.util.*;
 
class GFG 
{
 
    // Depth-First Search to find 
    // a connected component
    static void dfs(Vector<Integer>[] g, int[] vis, 
                              int[] odd, int[] deg,
                              int comp, int v) 
    {
        vis[v] = 1;
        if (deg[v] % 2 == 1)
            odd[comp]++;
        for (int u : g[v])
            if (vis[u] == 0)
                dfs(g, vis, odd, deg, comp, u);
    }
 
    // Return minimum edge required 
    // to make Euler Circuit
    static int minEdge(int n, int m, 
                       int[] s, int[] d)
    {
 
        // g : to store adjacency list
        //     representation of graph.
        // e : to store list of even degree vertices
        // o : to store list of odd degree vertices
        @SuppressWarnings("unchecked")
        Vector<Integer>[] g = new Vector[n + 1];
        Vector<Integer> e = new Vector<>();
        Vector<Integer> o = new Vector<>();
 
        for (int i = 0; i < n + 1; i++)
            g[i] = new Vector<>();
 
        // Degrees of vertices
        int[] deg = new int[n + 1]; 
         
        // To store visited in DFS
        int[] vis = new int[n + 1];
         
        // Number of odd nodes in components
        int[] odd = new int[n + 1]; 
        Arrays.fill(deg, 0);
        Arrays.fill(vis, 0);
        Arrays.fill(odd, 0);
 
        for (int i = 0; i < m; i++) 
        {
            g[s[i]].add(d[i]);
            g[d[i]].add(s[i]);
            deg[s[i]]++;
            deg[d[i]]++;
        }
 
        // 'ans' is result and 
        // 'comp' is component id
        int ans = 0, comp = 0;
        for (int i = 1; i <= n; i++) 
        {
            if (vis[i] == 0) 
            {
                comp++;
                dfs(g, vis, odd, deg, comp, i);
 
                // Checking if connected component
                // is odd.
                if (odd[comp] == 0)
                    e.add(comp);
 
                // Checking if connected component
                // is even.
                else
                    o.add(comp);
            }
        }
         
        // If whole graph is a single connected
        // component with even degree.
        if (o.size() == 0 && e.size() == 1)
            return 0;
 
        // If all connected component is even
        if (o.size() == 0)
            return e.size();
 
        // If graph have atleast one 
        // even connected component
        if (e.size() != 0)
            ans += e.size();
 
        // For all the odd connected component.
        for (int i : o)
            ans += odd[i] / 2;
 
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args) throws IOException
    {
        int n = 3, m = 2;
        int[] source = { 1, 2 };
        int[] destination = { 2, 3 };
 
        System.out.println(minEdge(n, m, source, 
                                   destination));
    }
}
 
// This code is contributed by
// sanjeev2552

Python3

# Python3 program to find minimum edge 
# required to make Euler Circuit
 
# Depth-First Search to find a 
# connected component 
def dfs(g, vis, odd, deg, comp, v):
    vis[v] = 1
 
    if (deg[v] % 2 == 1): 
        odd[comp] += 1
         
    for u in range(len(g[v])):
        if (vis[u] == 0):
            dfs(g, vis, odd, deg, comp, u)
 
# Return minimum edge required to
# make Euler Circuit 
def minEdge(n, m, s, d):
     
    # g : to store adjacency list 
    #      representation of graph. 
    # e : to store list of even degree vertices 
    # o : to store list of odd degree vertices 
    g = [[] for i in range(n + 1)]
    e = []
    o = []
 
    deg = [0] * (n + 1) # Degrees of vertices 
    vis = [0] * (n + 1) # To store visited in DFS 
    odd = [0] * (n + 1) # Number of odd nodes
                        # in components 
     
    for i in range(m):
        g[s[i]].append(d[i]) 
        g[d[i]].append(s[i]) 
        deg[s[i]] += 1
        deg[d[i]] += 1
 
    # 'ans' is result and 'comp' 
    # is component id 
    ans = 0
    comp = 0
    for i in range(1, n + 1):
        if (vis[i] == 0):
            comp += 1
            dfs(g, vis, odd, deg, comp, i) 
 
            # Checking if connected component 
            # is odd. 
            if (odd[comp] == 0): 
                e.append(comp) 
 
            # Checking if connected component 
            # is even. 
            else:
                o.append(comp)
 
    # If whole graph is a single connected 
    # component with even degree. 
    if (len(o) == 0 and len(e) == 1): 
        return 0
 
    # If all connected component is even 
    if (len(o) == 0): 
        return len(e) 
 
    # If graph have atleast one 
    # even connected component 
    if (len(e) != 0): 
        ans += len(e)
 
    # For all the odd connected component. 
    for i in range(len(o)):
        ans += odd[i] // 2
 
    return ans
 
# Driver Code
if __name__ == '__main__':
 
    n = 3
    m = 2
    source = [ 1, 2 ]
    destination = [ 2, 3]
 
    print(minEdge(n, m, source, destination))
 
# This code is contributed by PranchalK

C#

// C# program to find minimum edge
// required to make Euler Circuit
 
using System;
using System.Collections.Generic;
 
class Program
{
    // Depth-First Search to find 
    // a connected component
    static void DFS(List<int>[] g, int[] vis, int[] odd, int[] deg, int comp, int v)
    {
        vis[v] = 1;
        if (deg[v] % 2 == 1)
            odd[comp]++;
        foreach (var u in g[v])
            if (vis[u] == 0)
                DFS(g, vis, odd, deg, comp, u);
    }
   // Return minimum edge required 
    // to make Euler Circuit
    static int MinEdge(int n, int m, int[] s, int[] d)
    {
       // g : to store adjacency list
        //     representation of graph.
        // e : to store list of even degree vertices
        // o : to store list of odd degree vertices
        List<int>[] g = new List<int>[n + 1];
        List<int> e = new List<int>();
        List<int> o = new List<int>();
 
        for (int i = 0; i < n + 1; i++)
            g[i] = new List<int>();
    // Degrees of vertices
        int[] deg = new int[n + 1];
        int[] vis = new int[n + 1];
        int[] odd = new int[n + 1];
        Array.Fill(deg, 0);
        Array.Fill(vis, 0);
        Array.Fill(odd, 0);
 
        for (int i = 0; i < m; i++)
        {
            g[s[i]].Add(d[i]);
            g[d[i]].Add(s[i]);
            deg[s[i]]++;
            deg[d[i]]++;
        }
 // 'ans' is result and 
        // 'comp' is component id
        int ans = 0, comp = 0;
        for (int i = 1; i <= n; i++)
        {
            if (vis[i] == 0)
            {
                comp++;
                DFS(g, vis, odd, deg, comp, i);
     // Checking if connected component
                // is odd.
                if (odd[comp] == 0)
                    e.Add(comp);
                   // Checking if connected component
                // is even.
                else
                    o.Add(comp);
            }
        }
 // If whole graph is a single connected
        // component with even degree.
        if (o.Count == 0 && e.Count == 1)
            return 0;
    // If all connected component is even
        if (o.Count == 0)
            return e.Count;
 
        // If graph have atleast one 
        // even connected component
        if (e.Count != 0)
            ans += e.Count;
 // For all the odd connected component.
        foreach (var i in o)
            ans += odd[i] / 2;
 
        return ans;
    }
//Driver code
    static void Main(string[] args)
    {
        int n = 3, m = 2;
        int[] source = { 1, 2 };
        int[] destination = { 2, 3 };
 
        Console.WriteLine(MinEdge(n, m, source, destination));
    }
}

Javascript

// Javascript program to find minimum edge
// required to make Euler Circuit
 
// Depth-First Search to find 
// a connected component
function dfs(g, vis, odd, deg, comp, v) {
  vis[v] = 1;
 
  if (deg[v] % 2 == 1) {
    odd[comp]++;
  }
 
  for (let u of g[v]) {
    if (vis[u] == 0) {
      dfs(g, vis, odd, deg, comp, u);
    }
  }
}
// Return minimum edge required 
// to make Euler Circuit
function minEdge(n, m, s, d) {
  let g = Array.from(Array(n + 1), () => []); // Adjacency list representation of graph
  let e = []; // List of even degree vertices
  let o = []; // List of odd degree vertices
  let deg = Array(n + 1).fill(0); // Degrees of vertices
  let vis = Array(n + 1).fill(0); // Visited in DFS
  let odd = Array(n + 1).fill(0); // Number of odd nodes in components
 
  for (let i = 0; i < m; i++) {
    g[s[i]].push(d[i]);
    g[d[i]].push(s[i]);
    deg[s[i]]++;
    deg[d[i]]++;
  }
 
  let ans = 0; // Result
  let comp = 0; // Component ID
 
  for (let i = 1; i <= n; i++) {
    if (vis[i] == 0) {
      comp++;
      dfs(g, vis, odd, deg, comp, i);
 
      if (odd[comp] == 0) {
        e.push(comp);
      } else {
        o.push(comp);
      }
    }
  }
 
  if (o.length == 0 && e.length == 1) {
    return 0;
  }
 
  if (o.length == 0) {
    return e.length;
  }
 
  if (e.length != 0) {
    ans += e.length;
  }
 
  for (let i of o) {
    ans += Math.floor(odd[i] / 2);
  }
 
  return ans;
}
 
// Driven Program
const n = 3;
const m = 2;
const source = [1, 2];
const destination = [2, 3];
 
console.log(minEdge(n, m, source, destination));

Output

This article is contributed by Anuj Chauhan. If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!