J'essaie de vérifier si un graphique reste cyclique après la suppression d'un nœud. Dans cette tentative, j'éclate une clé et vérifie si la suppression de ce nœud supprime tous les cycles ou non. Mais peut-être qu'après la première pop, l'élément sauté n'est pas inséré

def detectCycle(v,visited,parent):
    visited[v]=True
    for i in Graph[v]:
        if(visited[i]==False):
            if(detectCycle(i,visited,v)):
                return True
        elif parent!=i:
            return True
    return False

def isCyclic():
    visited=[False for i in range(N+1)]
    for i in Graph.keys():
        if(visited[i]==False):
            if(detectCycle(i,visited,-1)==True):
                return True
    return False


Graph={1: [5, 2], 2: [5, 1, 3, 4], 3: [2], 4: [2], 5: [1, 2]}
N=len(Graph.keys())
flag=0
for i in range(1,N+1):            
        x=Graph.pop(i)
        if(isCyclic()):
            pass
        else:
            flag=1
            break
        Graph[i]=x
if(flag==1):
        print(i)
else:
        print(-1)

Je m'attends à ce que le nœud qui supprime le cycle soit supprimé et s'il n'existe pas, un tel nœud -1 est retourné, mais ce que je reçois est

Traceback (most recent call last):
    for i in Graph[v]:
KeyError: 1
0
Master Mind 4 nov. 2019 à 09:40