Last Updated: 9 Nov, 2021
Ninja's Trip
Moderate
Asked in companies
Ninja is new to the city, so he decided to explore the city. The city is in the form of an undirected graph having ‘N’ locations and ‘E’ roads. Ninja wants to visit the city in such a way that if he starts his journey from location ‘X’, he visits all the roads of the city exactly once and returns to the starting point ‘X’.Can you help Ninja to find either it is possible or not to have such a trip?
You are given an undirected graph having ‘N’ vertices and ‘E’ edges. You have to find either a round trip visiting all edges exactly once is possible or not.
For Example
For the given graph:
The required path exists in the given graph as we can start from 1 and follow the path 1 -> 0 -> 2 -> 1. This path visits all edges exactly once. Hence, the answer is YES.
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains two integers ‘N’ and ‘E’ denoting the number of vertices and edges.
The next ‘E’ lines have two integers denoting an edge between them.
Output Format:
For each test case, print ‘YES’ if the path with given condition is possible,else print ‘NO’.
Print the output of each test case in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
2 <= N <= 1000.
1 <= E <= min(N*(N-1)/2, 5000).
0 <= u,v < ‘N’
Time limit: 1 sec
Approaches
In this approach, we will Euler Circuit Detection to find either an Euler circuit is present in the graph or not.
In graph theory, Euler Circuit is defined as a path that starts and ends at the same vertex and traverse all edges of the graph exactly once.
An undirected graph has an Eulerian cycle if the following two conditions are true.
i) All vertices with non-zero degrees are connected.
ii) All vertices must have an even degree.
All vertices must have an even degree because to complete a cycle because for each incoming edge there must be an outgoing edge as we had to use each edge only once.
We will first store the graph in an adjacency list manner and then check the degrees of all vertices. If we found any vertex with an odd degree, the answer will be ‘FALSE’.After that, we will check either all the subgraphs having some edges are connected or not using depth-first traversal. If they are connected, both the conditions are satisfied, return ‘TRUE’.Else , return ‘FALSE’.
Algorithm:
- Defining DFS(‘CUR’,’ G’ ,’ VIS’) is a standard DFS function for traversal in graph G.
- Set ‘CUR’ node as visited.
- Set VIS[‘CUR’] as 1.
- For i in G[‘CUR’], do the following:
- IF VIS[i] is 0:
- Call DFS(‘i’,‘G’,’VIS’).
- IF VIS[i] is 0:
- Declare an array of dynamic arrays ‘G’ to store the graph in an adjacency list manner.
- For ‘EDGE’ in ‘EDGES’:
- Append ‘EDGE[0]’ into ‘G[EDGE[1]]’.
- Append ‘EDGE[1]’ into ‘G[EDGE[1]]’.
- Check for any vertex with an odd degree.
- For i in range 0 to ‘N’-1:
- If the size of G[i] is odd, return ‘FALSE’.
- Declare a ‘VIS’ array to store whether the vertex is visited or not.
- Set all values of ‘VIS’ to 0.
- For i in range 0 to ‘N’-1:
- If the size of G[i] is greater than 0:
- Call DFS(i,’G’,’VIS’).
- Break.
- If the size of G[i] is greater than 0:
- For i in range 0 to ‘N’-1:
- If the size of G[i] is greater than 0 and ‘VIS[i]’ is 0:
- If implies that vertex with the non-zero degree is not connected.
- Return ‘FALSE’.
- If the size of G[i] is greater than 0 and ‘VIS[i]’ is 0:
- Return ‘TRUE’.