Problem P: Given an undirected graph G=(V,E) where V is the set of nodes and E is the set of edges and where |V|=n and |E|=m, we want to determine if the graph G, entered by the user, has at least one cycle or not. As studied in the class, a cycle in a graph G is defined as a closed chain of nodes where the first node and the last node in the chain are the same, in another word the only repeated nodes are the first and the last nodes in the closed chain or cycle. You may assume that graph G is connected, has no parallel edges and self-loops.
Task: Write a C++/Java program to solve problem P defined above. Your program should return true if the graph has at least a cycle, and false otherwise. The runtime of your program should not be exponential but it's fine if it is not the best possible algorithm you may write to solve the problem (Try to write the algorithm as efficient as you can in respect to the time complexity and even space though).
Examples of user input:
Example 1: see image.
The output of the algorithm should be true, as 3-2-4-3 is a cycle.
Example 2: see image.
The output of the algorithm should be false.
The format for the input to your program should be the list of the edges, each in one line. For example for below graph the input will look like (you may use * as a sign showing the end of the input): see image.
Input:
1,2
2,3
3,4
4,2
2,3
*
Similarly, for below graph: see image.
The input will be:
1,4
6,4
5,4
3,4
2,3
*