Проверьте список ребер, является ли он циклическим c или нет в python - PullRequest
Новая
       54

Проверьте список ребер, является ли он циклическим c или нет в python

0 голосов
/ 14 апреля 2020

У меня возникла проблема при решении этой проблемы, но я не знаю, почему мой код не смог пройти все тестовые случаи.

Из заданного списка ребер проверьте, циклично ли оно c или нет.

Пример:

Для Edges = ["AB", "B- C"] ("A", "B", "C - узлы), вывод должен быть ложным.

Мы можем начать с A до B до C, но не можем вернуться к A. Таким образом, ответ ложен

Для Edges = ["A1-B", "B - C "," a1- C "], вывод должен быть истинным (" A1 "и" a1 "не отличаются)

Вот мой код, но это не так t работают хорошо. 

Vertices = {}
def updateConnection(old,new):
    for k,v in Vertices.items():
        if v == old:
            Vertices[k] = new

def unite(v1,v2):
    newpid = Vertices[v1]
    oldpid = Vertices[v2]
    updateConnection(oldpid,newpid)
def isConnected(v1,v2):
    return Vertices[v1] == Vertices[v2]

def isCyclic(Edges):
    for i in range(len(Edges)):
        Edges[i] = Edges[i].lower()
        Edges[i] = Edges[i].split('-')
    for edge in Edges:
        if not edge[0] in Vertices.keys():
            Vertices[edge[0]] = edge[0]
        if not edge[1] in Vertices.keys():
            Vertices[edge[1]] = edge[1]
        if isConnected(edge[0],edge[1]):
            return True
        unite(edge[0],edge[1])
    return False

Больше тестов: 

# Input : 
["a-b", "b-c"]
# Expected output: False

# Input :
["Ab-bc", "bC-ca", "aB-cd", "cd-Ca"]
# Expected output: True
...