Как посчитать связанные компоненты, образующие циклы в неориентированном графе? ⇐ Python

[Anonymous]

Я работаю с неориентированным графом, и мне нужно определить количество связных компонентов, которые также являются циклами. Цикл определяется как связный компонент, в котором каждая вершина имеет ровно два ребра, а компонент содержит не менее трех вершин.
Граф представлен n вершинами и m< /код> края. Каждое ребро соединяет две разные вершины, дубликаты ребер отсутствуют.

Определения:

• Неориентированный граф:
  • Состоит из двух наборов: одного из вершин и другого из ребер.
  • Каждое ребро соединяет две различные вершины (( u \neq v )).
  • Между любой парой вершин существует не более одного ребра.
• Связной компонент:
  • Подмножество вершин, в котором любые две вершины в этом подмножестве соединены путь, и подмножество не связано ни с какой другой вершиной за его пределами.
• Цикл:
  • Компонента связности является циклом, если:
    
    Он содержит не менее 3 вершин.
  • Каждая вершина является частью ровно 2 ребер.
  • Переставляя его вершины, можно сформировать последовательность, в которой первая вершина соединяется с вторая, вторая с третьей, ... и последняя вершина снова соединяется с первой.

Ввод:

• Первая строка содержит два целых числа. , n (1 ≤ n ≤ 200 000) и m (0 ≤ m ≤ 200 000), представляющее количество вершин и ребер.
• Следующие m строк содержат по два целых числа, u и v, описывающих ребро. между вершиной u и вершиной v. Повторяющихся ребер нет, граф неориентированный.

Вывод:

• Одно целое число: количество связанных компонентов в графе, которые являются циклами.

Пример:

Ввод :

Код: Выделить всё

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

Выход:

Код: Выделить всё

2

Моя попытка:

Я реализовал следующее решение Python, которое работает в некоторых случаях, но не работает в некоторых скрытых тестовых случаях на платформе подачи заявок моего университета. Вот код, который я использовал:

Код: Выделить всё

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))

Есть идеи, почему этот код может не работать в определенных тестовых случаях? И как это можно исправить или оптимизировать, чтобы это исправить?


Подробнее здесь: https://stackoverflow.com/questions/793 ... cted-graph