Ninja's Trip

Moderate
0/80
6 upvotes
Asked in companies
Media.netFlipkart limitedTower Research Capital

Problem statement

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:

alt-text

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3 3
0 1
1 2
2 0
Sample Output 1:
YES
YES
Explanation of sample input 1:
For the first test case,

alt-text

The path 1 -> 0 -> 2 -> 1 fulfills all the requirements.Hence the answer is ‘YES’.

For the second test case:

alt-text

The path 1 -> 0 -> 4 -> 3 ->0 ->2 -> 1 fulfills all the requirements.Hence the answer is ‘YES’.

Sample Input 2:
2
2 1
0 1
3 1
0 1
Sample Output 2:
NO
NO
Hint

Try to observe a pattern in about the degree of each vertex.

Approaches (1)
Euler Circuit Detection

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’).


 

  • 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.
  • 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’.
  • Return ‘TRUE’.
Time Complexity

O(N+E), where ‘N’ is the number of locations and ‘E’ is the number of roads.

 

In this approach, we are calling a DFS() function to check whether the subgraphs are connected or not, which takes O(N + E) time. Apart from we are checking the degrees of all vertices which takes O(N) time. Hence, the overall time complexity is O(N+E).

Space Complexity

O( N+E ), where ‘N’ is the number of locations and ‘E’ is the number of roads.

 

In this approach, in the worst case, stack memory of O(N) will be used in dfs recursion and O(E) space is used to store the graph in an adjacency list manner, Hence, the overall space complexity is O(N+E).

Code Solution
(100% EXP penalty)
Ninja's Trip
Full screen
Console