Найти - Пользователи
Полная версия: Поиск цикла в графе
Начало » Центр помощи » Поиск цикла в графе
1
Andrew22528
Есть ориентированный граф. На вход подается 2 числа N и M - количества вершин и рёбер в графе соответственно. Далее в M строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин. Надо вывести ‘YES’ и номера вершин в цикле, если цикл есть. Иначе вывести ‘NO’. Заранее спасибо
Isem
Взято из библиотеки bytenet3
import collections, itertools
def get_loops(MN):
    """ Returns the tuple of closed loops. Loops are represented as ordered lists of nodes """
    network = {}
    for a,b in MN:
        network[a].add(b) if a in network else network.update({a:{b}})
        network[b].add(a) if b in network else network.update({b:{a}})
    chain = collections.OrderedDict()
    def __loop_iterator(node):
        if node not in chain:
            chain[node] = None
            next = network[node]
            while next:
                n = next.pop()
                network[n].remove(node)
                yield from __loop_iterator(n)
            chain.popitem()
        else: yield tuple(itertools.chain(itertools.takewhile(lambda x: x is not node, reversed(chain)), (node,)))
    # 'for' is needed for just to run from any first available node as n
    for n in network: return tuple(__loop_iterator(n))
    
ch = [(1,4), (4,3), (3,2), (6,3), (4,6), (5,6), (5,4)]
>>> print( *get_loops(ch), sep = '\n' )
(6, 3, 4)
(5, 6, 3, 4)
This is a "lo-fi" version of our main content. To view the full version with more information, formatting and images, please click here.
Powered by DjangoBB