91Ó°ÊÓ

A linear-time algorithm is one in which the method's execution time is proportional to the amount of the input.The aim of the questions is to determine whether or not there is a cycle in the graph $\mathrm{G}(\mathrm{V},\mathrm{E})$.

Here, V is the vertex set and E is the edge set of the graph G .

If there is no cycle in the graph, there is only one route from one vertex to the other vertex. So, deleting an edge will result in unconnected components.

The only way to remove an edge from a graph without disconnecting it is if the graph has a cycle. In such instance, one of the cycle's edges can be deleted without causing the graph to be disconnected. The number of edges in a graph with no cycle is equal to one less than the number of vertices. The algorithm return 1, if deleting an edge does not disconnects the graph. Otherwise, the algorithm return 0. The algorithm is as follows:

1. Calculate the number of vertices in the graph and store it in a variablecv.
2. Calculate the number of edges in the graph and store it in a variablece.
3. If the value ofceis higher than or equal tocv, return 1
4. Else return 0

Calculating the number of vertices and edges in the graph takes the linear time.

Run the recursive graph traversal. While traversing the graph, the visited nodes are marked. Whenever the already visited node is encountered, the graph traversal return true. The whole graph is traversed if it does not contain cycle. The cycle is found in the graph after traversing edges equal to the number of vertices. The run time of the algorithm can be reduced to${}^{\left(O\left|V\right|\right)}$.