Wie zählt man zusammenhängende Komponenten, die Kreise in einem ungerichteten Diagramm bilden? ⇐ Python

[Anonymous]

Ich arbeite mit einem ungerichteten Graphen und muss die Anzahl der verbundenen Komponenten bestimmen, die auch Zyklen sind. Ein Zyklus ist als verbundene Komponente definiert, bei der jeder Scheitelpunkt genau zwei Kanten hat und die Komponente mindestens drei Scheitelpunkte enthält.
Der Graph wird durch n Scheitelpunkte und m< dargestellt /code> Kanten. Jede Kante verbindet zwei unterschiedliche Eckpunkte und es gibt keine doppelten Kanten.

Definitionen:

• Ungerichteter Graph:
  • Bestehend aus zwei Mengen: einer aus Eckpunkten und der anderen aus Kanten.
  • Jede Kante verbindet zwei verschiedene Eckpunkte (( u \neq v )).
  • Es gibt höchstens eine Kante zwischen jedem Scheitelpunktpaar.
• Verbundene Komponente:
  • Eine Teilmenge von Scheitelpunkten, sodass zwei beliebige Scheitelpunkte in dieser Teilmenge durch a verbunden sind Pfad, und die Teilmenge ist mit keinem anderen Scheitelpunkt außerhalb davon verbunden.
• Zyklus:
  • Eine zusammenhängende Komponente ist ein Kreis, wenn:
    
    Sie mindestens 3 Eckpunkte enthält.
  • Jeder Eckpunkt ist Teil von genau 2 Kanten.
  • Durch Neuanordnen der Scheitelpunkte kann eine Sequenz gebildet werden, mit der der erste Scheitelpunkt verbunden ist der zweite, der zweite mit dem dritten, ... und der letzte Scheitelpunkt verbindet sich wieder mit dem ersten.

Eingabe:

• Die erste Zeile enthält zwei Ganzzahlen , n (1 ≤ n ≤ 200.000) und m (0 ≤ m ≤ 200.000), die die Anzahl der Scheitelpunkte und Kanten darstellt.
• Die nächsten m-Zeilen enthalten jeweils zwei Ganzzahlen, u und v, die beschreiben eine Kante zwischen Scheitelpunkt u und Scheitelpunkt v. Es gibt keine doppelten Kanten und der Graph ist ungerichtet.

Ausgabe:

• Eine einzelne Ganzzahl: die Anzahl der verbundenen Komponenten im Diagramm, die Zyklen sind.

Beispiel:

Eingabe :
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

Ausgabe:
2

Mein Versuch:

Ich habe die folgende Python-Lösung implementiert, die in einigen Fällen funktioniert, aber bei bestimmten versteckten Testfällen in der Einreichungsplattform meiner Universität fehlschlägt. Hier ist der Code, den ich verwendet habe:
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.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))

Irgendeine Idee, warum dieser Code in bestimmten Testfällen möglicherweise fehlschlägt? Und wie kann es korrigiert oder optimiert werden, um dies zu beheben?