โปรแกรมตรวจสอบว่ามีวัฏจักรความยาวคี่ในกราฟหรือไม่ใน Python

สมมติว่าเรามีกราฟไม่มีทิศทาง (undirected graph) ต้องการตรวจสอบว่ามีวัฏจักร (cycle) ที่มีความยาวเป็นเลขคี่ (odd length cycle) หรือไม่

เช่น adj_list = [[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]] ผลลัพธ์ = True มีวัฏจักรคี่ เช่น [0, 1, 3, 4, 2], [1, 3, 4], [2, 3, 4]

ขั้นตอนการแก้ปัญหา (DFS + Depth Parity)

• ฟังก์ชัน dfs(node, i) โดย i = ความลึก:
  • ถ้า node in path: คืน True ถ้า (i - path[node]) % 2 == 1 (ความยาววัฏจักรคี่)
  • ถ้า node in visited: คืน False
  • mark visited, path[node] = i
  • วนเพื่อนบ้าน c ใน arr[node]: ถ้า dfs(c, i+1) คืน True
  • ลบ path[node], คืน False
• จากเมธอดหลัก: visited=set(), path={} วน i=0..len(arr)-1 ถ้า dfs(i,0) คืน True

ตัวอย่างโค้ด

class Solution:
    def solve(self, arr):
        def dfs(node, i):
            if node in path:
                return (i - path[node]) % 2 == 1
            if node in visited:
                return False
            visited.add(node)
            path[node] = i
            for c in arr[node]:
                if dfs(c, i + 1):
                    return True
            del path[node]
            return False
        visited, path = set(), {}
        for i in range(len(arr)):
            if dfs(i, 0):
                return True
        return False

ob = Solution()
adj_list = [[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]]
print(ob.solve(adj_list))

ข้อมูลนำเข้า

[[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]]

ผลลัพธ์

True