Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Euler Path

Hard
0/120
Average time to solve is 15m
profile
Contributed by
8 upvotes
Asked in companies
AmazonSprinklrFlipkart

Problem statement

You are given an undirected graph 'EDGE_LIST' of ‘N’ nodes and ‘M’ edges. Your task is to return any Euler path of the graph. If no Euler path exists then you need to return -1.

Note :
An Euler path is a path in a graph such that every edge must be visited exactly once. You can visit the same vertex multiple times. 
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
1 <= T <= 5
1 <= N <= 100
1 <= M <= min(100, N*(N-1)/2)
0 <= U, V <= N - 1

Time Limit: 1 sec
Sample Input 1:
2
3 2
0 1
0 2
4 5
0 1
0 2
0 3
1 2
2 3
Sample Output 1:
1
1
Explanation of Sample Input 1:
Test Case 1 :  
The given graph is shown below. 

1

Euler path = 1 -> 0 -> 2
Also, 2 -> 0 -> 1 is also a valid Euler path.
If we return any one of the above two paths then we will get output as 1.

Test Case 2 : 
The given graph is shown below.

2

Euler path = 2 -> 0 -> 1 -> 2 -> 3 -> 0 
If we return the above path then we will get output as 1.

Note : Here we have visited node 0 and 2 multiple times but we have visited each edge exactly once.
Sample Input 2:
2
5 4
0 4
0 1
1 3
1 2
5 4
0 1
1 2
2 3
3 4
Sample Output 2:
1
1
Explanation of Sample Input 2:
Test Case 1 :  
The given graph is shown below. 

3

There is no Euler path possible for the above graph. So, we need to return -1.

Test Case 2 : 
The given graph is shown below.

4

Euler path = 0 -> 1 -> 2 -> 3 -> 4
Full screen
Console