I am working with an undirected graph and need to determine the number of connected components that are also cycles. A cycle is defined as a connected component where each vertex has exactly two edges, and the component contains at least three vertices.

The graph is represented by n vertices and m edges. Each edge connects two distinct vertices, and there are no duplicate edges.

Definitions:

1. Undirected Graph:

   • Composed of two sets: one of vertices and the other of edges.
   • Each edge connects two distinct vertices (( u neq v )).
   • There is at most one edge between any pair of vertices.

2. Connected Component:

   • A subset of vertices such that any two vertices in this subset are connected by a path, and the subset is not connected to any other vertex outside of it.

3. Cycle:

   • A connected component is a cycle if:
     • It contains at least 3 vertices.
     • Each vertex is part of exactly 2 edges.
     • Rearranging its vertices can form a sequence such that the first vertex connects to the second, the second to the third, …, and the last vertex connects back to the first.

Input:

• The first line contains two integers, n (1 ≤ n ≤ 200,000) and m (0 ≤ m ≤ 200,000), representing the number of vertices and edges.
• The next m lines each contain two integers, u and v, describing an edge between vertex u and vertex v. There are no duplicate edges, and the graph is undirected.

Output:

• A single integer: the number of connected components in the graph that are cycles.

Example:

Input:

17 15
1 8
1 12
5 11
11 9
9 15
15 5
4 13
3 13
4 3
10 16
7 10
16 7
14 3
14 4
17 6

Output:

2

My Attempt:

I implemented the following Python solution, which works for some cases but fails for certain hidden test cases in my university’s submission platform. Here’s the code I used:

from collections import defaultdict, deque

def count_cycle_components(n, m, edges):
    # Create an adjacency list for the graph
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    # Visited array to track visited nodes
    visited = [False] * (n + 1)

    # Helper function to check if a connected component is a cycle
    def is_cycle_component(node):
        queue = deque([(node, -1)])  # (current node, parent node)
        visited[node] = True
        node_count = 0
        edge_count = 0

        while queue:
            current, parent = queue.popleft()
            node_count += 1
            for neighbor in graph[current]:
                edge_count += 1
                if not visited[neighbor]:
                    visited[neighbor] = True
                    queue.append((neighbor, current))
                elif neighbor != parent:
                    pass  # Neighbor visited and not parent, ignore
        
        # Each edge is counted twice in an undirected graph
        edge_count //= 2

        # Check if the connected component is a cycle
        return node_count >= 3 and edge_count == node_count

    cycle_count = 0

    # Iterate through all nodes to find connected components
    for node in range(1, n + 1):
        if not visited[node]:
            if is_cycle_component(node):
                cycle_count += 1

    return cycle_count

if __name__ == "__main__":
    import sys
    input = sys.stdin.read
    data = input().splitlines()

    # Read the number of vertices and edges
    n, m = map(int, data[0].split())
    # Read the edges
    edges = [tuple(map(int, line.split())) for line in data[1:]]

    # Output the number of cycle components
    print(count_cycle_components(n, m, edges))

Any idea why does this code might fail for certain test cases? And how can it be corrected or optimized to fix this?