def eulerkreis(graph):
    kreisExistiert = True
    startKnoten = graph[0][0]
    zuBesuchen = [startKnoten]
    besucht = []
    while zuBesuchen != [] and kreisExistiert:
        knoten = zuBesuchen[0]
        # bestimme die Anzahl der Nachbarn von knoten
        knotenGefunden = False
        i = 0
        while not knotenGefunden:
            if knoten == graph[i][0]:
                knotenGefunden = True
                listeNachbarknoten = graph[i][1]
            i = i+1
        anzahlNachbarn = len(listeNachbarknoten)
        # Test, ob die Anzahl ungerade ist
        if anzahlNachbarn % 2 == 1:
            kreisExistiert = False
        zuBesuchen = zuBesuchen[1:]
        besucht = besucht + [knoten]
        # Hinzufügen der Nachbarknoten
        for nachbarKnoten in listeNachbarknoten:
            if not nachbarKnoten in besucht:
                zuBesuchen = zuBesuchen + [nachbarKnoten]
    if len(besucht) < len(graph):
        kreisExistiert = False
    return kreisExistiert

# Testdaten

graph1 = [
    ['1', ['2', '3']],
    ['2', ['1', '5', '4', '3']],
    ['3', ['2', '4', '5', '1']],
    ['4', ['2', '3']],
    ['5', ['2', '3']]
]

graph2 = [
    ['1', ['2', '3', '7', '8']],
    ['2', ['1', '3']],
    ['3', ['2', '1', '8', '4']],
    ['4', ['3', '7', '9', '5']],
    ['5', ['9', '4']],
    ['6', ['7', '9']],
    ['7', ['1', '4', '9', '6']],
    ['8', ['1', '3']],
    ['9', ['4', '7', '6', '5']],
]

from random import *

def graph(n):
    graph = []
    for i in range(n):
        nachbarn = []
        for j in range(n):
            nachbarn = nachbarn + [randint(0, n-1)]
        graph = graph + [[i, nachbarn]]
    return graph


# Test

#print(eulerkreis(graph1))

from time import *

knotenzahl = 10
testgrenze = 1000
while knotenzahl < testgrenze:
        aktuellerGraph = graph(knotenzahl)
        t1 = process_time()
        kreisExistiert = eulerkreis(aktuellerGraph)
        t2 = process_time()
        t = t2 - t1
        print(knotenzahl, t)
        knotenzahl = knotenzahl * 2