## Introduction ⚔️

Hey Ninja!! 🥷You must have used google maps to find the best way to reach your destination. The underlying algorithm heavily depends on graph traversal techniques and uses a logic similar to the one we will explore.

In this article, we will learn about the Euler circuit and how to complete it if it is not in its correct state. Grab a cup of coffee, and let us jump right into the details of this advanced graph concept!! ☕

### Euler Circuit 💡

An Euler circuit is an Euler path formed when all the graph nodes have even degrees. i.e. if we consider one edge to enter into the node, there should exist a way to exit it.

In other words, it is an eulerian circuit if you can visit all the nodes without lifting the pen from the paper and all nodes are covered. The image below is an example of an Euler circuit.

### Problem Statement 🔔

Given a graph with V vertices and M edges, your task is to find the minimum number of edges required to make the graph an Euler circuit.

For example, look at the graph below:

The graph contains all even degree nodes except the node with value **'3'**, so if we connect node **1** with **3**, we can form an **Euler circuit**. Hence the answer here would be **1**.

## Approach 👀

Let us go through the steps needed to find the number of required edges:

**Case 1:** The graph contains only one connected component.

- If there is no node with an odd degree, then we don't need to do anything because the graph is already in eulerian form.
- If odd-degree edges are there, randomly select pair of nodes and add an edge between them. It can be easily proved that an even number of odd-degree nodes will exist.

**Case 2: **There is more than one component in the graph.

- First of all, find if the component is even or odd.
- Take all the even components and add edges between them. Since a node will be connected to two other nodes, the degree will remain even.
- After connecting all even components, it becomes an odd component.
- Circularly connect all odd components to obtain an Euler circuit.

**Steps:**

- Create a graph in the form of an adjacency list.
- Add edges and call the
**minEdges**function. -
Calculate degrees and call the
__DFS Algorithm__function for each component. - Count the number of odd and even components.
- Calculate the answer based on the number of odd and even components.

### Code Implementation 💻

In this section, we will walk through the code implementation in C++. Proper comments are added for ease of understanding:

```
// Coding Ninjas: Graph
#include<bits/stdc++.h>
using namespace std;
//function to add edges to graph
void addEdge(int a,int b,vector<vector<int>>&graph){
graph[a].push_back(b);
graph[b].push_back(a);
}
//DFS to find connected components
void DFS(vector<vector<int>>&graph,vector<bool>&visited,vector<int>&oddNodes,vector<int>°ree,int componentID,int V){
visited[V]=true;
//checking if the degree of a node is even or odd
if(degree[V]%2!=0){
oddNodes[componentID]++;
}
for(auto p:graph[V]){
if(!visited[p]){
DFS(graph,visited,oddNodes,degree,componentID,p);
}
}
}
int minEdges(vector<vector<int>>&graph,int V,int E){
vector<int>degree(V+1,0);
vector<bool>visited(V+1,false);
vector<int>oddNodes(V+1,0);
int countEvenComponents=0,countOddComponents=0;
int ans=0,componentID=0;
//calculating degrees for each vertex
for(int i=1;i<=V;i++){
degree[i]=graph[i].size();
}
//loop to go through each node
for(int i=1;i<=V;i++){
if(!visited[i]){
componentID++;
DFS(graph,visited,oddNodes,degree,componentID,i);
if(oddNodes[componentID]==0)
countEvenComponents++;
else
countOddComponents++;
}
}
//calculating answer based on the number of even and odd components
if(countOddComponents==0&&countEvenComponents==1)
return 0;
else if(countOddComponents==0)
return countEvenComponents;
else if(countEvenComponents!=0)
ans+=countEvenComponents;
for(auto p:oddNodes){
if(p!=0){
ans+=p/2;
}
}
return ans;
}
int main() {
int Vertices=5;
int Edges=5;
//graph in the form of adjacency list
vector<vector<int>>graph(6);
addEdge(1,2,graph);
addEdge(3,2,graph);
addEdge(1,4,graph);
addEdge(1,5,graph);
addEdge(5,4,graph);
cout<<"The minimum edges added by Ninja to make eulerian circuit: "<<minEdges(graph, Vertices, Edges);
return 0;
}
```

**Output:**

####
Complexity Analysis ⏰

**Time Complexity: O(V+E), ** where V and E are the numbers of vertices and edges, respectively. Time taken by this algorithm if the graph is represented using adjacency matrix representation is the same as DFS traversal.

**Space Complexity:** **O(V+E),** where V is the number of vertices and E is the number of edges in the graph. We have to maintain a visited array and list of size V.