cp_library/alg/graph/floyds_cycle_fn.py

• View this file on GitHub
• Last update: 2025-03-30 20:17:47+09:00

Required by

• cp_library/alg/graph/edmonds_fn.py

Verified with

• test/aoj/grl/grl_2_b_edmonds_branching.test.py

Code

import cp_library.alg.graph.__header__

def floyds_cycle(F, root):
    slow = fast = root
    while F[fast] != -1 and F[F[fast]] != -1:
        slow, fast = F[slow], F[F[fast]]
        if slow == fast:
            cyc = [slow]
            while F[slow] != cyc[0]:
                slow = F[slow]
                cyc.append(slow)
            return cyc
    return None

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''

def floyds_cycle(F, root):
    slow = fast = root
    while F[fast] != -1 and F[F[fast]] != -1:
        slow, fast = F[slow], F[F[fast]]
        if slow == fast:
            cyc = [slow]
            while F[slow] != cyc[0]:
                slow = F[slow]
                cyc.append(slow)
            return cyc
    return None

Back to top page