Approach to Detect Cycles in a Graph
The idea is quite simple. Since the graph may consist of multiple connected components, we need to ensure that we iterate each component individually. Run DFS or BFS on each unvisited node, keeping track of the parent of each node and marking it as visited. If you visit a node that has already been visited and it is not your parent, this implies that the graph contains a cycle.
Tom Riddle's Diary
In this problem, it was necessary to calculate the degrees of each vertex and find the answer. Note that since n > = 4 , m > = 3 and the graph is connected, the answer is unambiguous.
1) all degrees 2 and two vertices have degree 1 — a tire.
2) all degrees 2 — a ring.
3) all degrees 1 and one has degree > 2 — a star.
4) otherwise unknown.
Auto comment: topic has been updated by Adam_Jardali (previous revision, new revision, compare).