ข้อ 45 · LC1466 Reorder Routes to Make All Paths Lead to the City Zero (กลับทิศถนนไปเมือง 0) 🟡

โจทย์ (LC1466): มี n เมืองเลข 0 ถึง n-1 และถนน n-1 เส้น ซึ่งเชื่อมทุกเมืองเป็นรูปแบบ tree (เดินทางระหว่างเมืองสองเมืองใดก็มีเส้นทางเดียวเท่านั้น) กระทรวงคมนาคมตัดสินใจกำหนดทิศทางเดินรถทางเดียวให้ถนนทุกเส้นเพราะถนนแคบเกินไป ถนนแทนด้วย connections โดย connections[i] = [ai, bi] หมายถึงถนนจากเมือง ai ไปเมือง bi ปีนี้จะมีงานใหญ่ที่เมืองหลวง (เมือง 0) และมีคนอยากเดินทางไปที่นั่นจำนวนมาก งานของคุณคือกลับทิศถนนบางเส้นเพื่อให้ทุกเมืองสามารถเดินทางไปเมือง 0 ได้ ให้ return จำนวนถนนน้อยที่สุดที่ต้องเปลี่ยนทิศทาง

แนวทาง — ต้องใช้อะไร & คิดยังไง

ใช้ DFS บน graph ที่เก็บทั้งสองทิศแต่ติดป้าย cost (น้ำหนัก) กุญแจของข้อนี้คือ มองกลับด้าน เราอยากให้ทุกเมืองไปถึงเมือง 0 แต่คิดแบบนั้นตรง ๆ ยาก จึงกลับมุมเป็น ถ้าเราออกเดินจากเมือง 0 ไปหาทุกเมือง ถนนเส้นไหนที่เราเดินสวนทิศของมัน เส้นนั้นแหละที่ต้องกลับทิศ เพราะในสภาพจริงเมืองปลายทางจะเดินย้อนกลับมาหาเมือง 0 ไม่ได้

ถ้าเก็บ graph ตามทิศจริงอย่างเดียว DFS จากเมือง 0 จะเดินไปไม่ทั่วเพราะบางถนนชี้เข้าหา 0 ทริกคือใส่ทั้งสอง edge (แบบ undirected ไม่มีทิศ) เพื่อให้ traverse (เดินไล่) ได้ทั่ว tree แต่ติดป้าย cost ไว้ edge ทิศจริง (a→b ตามที่โจทย์ให้) ติด cost 1 ส่วน edge ปลอมที่เราเติมเพื่อเดินย้อน (b→a) ติด cost 0

1. สร้าง graph สำหรับแต่ละ [a,b] เพิ่ม (b, 1) ให้ a และเพิ่ม (a, 0) ให้ b
2. ตั้ง visited (เคยเยือน) และตัวนับ changes = 0
3. เขียน dfs(city) mark city แล้ว iterate (วน) เพื่อนบ้าน (neighbor) (nxt, cost)
4. ถ้า nxt ยังไม่ visited บวก changes ด้วย cost (ถ้าเป็น edge ทิศจริงจะบวก 1) แล้ว dfs(nxt) ต่อ
5. เรียก dfs(0) เริ่มเดินจากเมือง 0 ออกไปทุกทิศ
6. คืน changes

from collections import defaultdict

def min_reorder(n, connections):
    graph = defaultdict(list)
    for a, b in connections:
        graph[a].append((b, 1))   # ทิศจริง a->b : ถ้าเดินทางนี้จาก 0 ออกไป ต้องกลับ (cost 1)
        graph[b].append((a, 0))   # ทิศปลอมเพิ่มเข้ามาเพื่อเดินได้ทั่ว (cost 0)

    visited = set()
    changes = 0

    def dfs(city):
        nonlocal changes
        visited.add(city)
        for nxt, cost in graph[city]:
            if nxt not in visited:
                changes += cost    # ถ้า edge นี้เป็นทิศจริง (ชี้ออกจาก 0) ต้องกลับ
                dfs(nxt)

    dfs(0)                         # เริ่มเดินจากเมือง 0 ออกไปทุกทิศ
    return changes

print(min_reorder(6, [[0, 1], [1, 3], [2, 3], [4, 0], [4, 5]]))  # 3
print(min_reorder(5, [[1, 0], [1, 2], [3, 2], [3, 4]]))          # 2

3
2