Sắp xếp tô pô (Topological Sort)

from collections import defaultdict, deque

def topo_sort_kahn(n, canh):
    """
    Sắp xếp tô pô bằng thuật toán Kahn.
    Trả về danh sách thứ tự hợp lệ, hoặc [] nếu có chu trình.

    n: số đỉnh (0-indexed)
    canh: [(u, v)] — cạnh hướng từ u đến v
    """
    graph   = defaultdict(list)
    in_deg  = [0] * n

    for u, v in canh:
        graph[u].append(v)
        in_deg[v] += 1

    # Bắt đầu từ tất cả đỉnh có bậc vào = 0
    queue  = deque(i for i in range(n) if in_deg[i] == 0)
    result = []

    while queue:
        u = queue.popleft()
        result.append(u)
        for v in graph[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                queue.append(v)

    # Nếu không lấy đủ n đỉnh → có chu trình
    if len(result) == n:
        return result
    else:
        return []    # Chu trình phát hiện

# Ví dụ: 6 môn học (0-5)
# 0=Toán, 1=LtrCB, 2=Giaitich, 3=DSTS, 4=CTDL, 5=ToiUu
canh = [(0,2),(0,3),(1,4),(2,5),(3,5),(4,5)]
thu_tu = topo_sort_kahn(6, canh)
print("Thứ tự học:", thu_tu)    # Một kết quả hợp lệ: [0, 1, 2, 3, 4, 5]

# Test đồ thị có chu trình
canh_chu_trinh = [(0,1),(1,2),(2,0)]
print("Chu trình:", topo_sort_kahn(3, canh_chu_trinh))   # []

from collections import defaultdict

def topo_sort_dfs(n, canh):
    """
    Sắp xếp tô pô bằng DFS.
    Trả về (thứ_tự, có_chu_trình).
    """
    graph = defaultdict(list)
    for u, v in canh:
        graph[u].append(v)

    # Trạng thái: 0=chưa thăm, 1=đang thăm, 2=xong
    state = [0] * n
    stack = []
    co_chu_trinh = [False]

    def dfs(u):
        if co_chu_trinh[0]:
            return
        state[u] = 1                # Đang thăm
        for v in graph[u]:
            if state[v] == 1:        # Gặp đỉnh đang thăm → chu trình
                co_chu_trinh[0] = True
                return
            if state[v] == 0:
                dfs(v)
        state[u] = 2                # Xong
        stack.append(u)             # Đẩy vào stack SAU KHI xong

    for i in range(n):
        if state[i] == 0:
            dfs(i)

    if co_chu_trinh[0]:
        return [], True
    return stack[::-1], False       # Đảo ngược stack

canh = [(0,2),(0,3),(1,4),(2,5),(3,5),(4,5)]
thu_tu, cycle = topo_sort_dfs(6, canh)
print("Thứ tự:", thu_tu)
print("Có chu trình:", cycle)

from collections import defaultdict, deque

def la_dag(n, canh):
    """Trả về True nếu đồ thị có hướng không có chu trình."""
    graph  = defaultdict(list)
    in_deg = [0] * n
    for u, v in canh:
        graph[u].append(v)
        in_deg[v] += 1
    q = deque(i for i in range(n) if in_deg[i] == 0)
    count = 0
    while q:
        u = q.popleft()
        count += 1
        for v in graph[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                q.append(v)
    return count == n

print(la_dag(4, [(0,1),(1,2),(2,3)]))           # True
print(la_dag(3, [(0,1),(1,2),(2,0)]))           # False (chu trình)
print(la_dag(5, [(0,1),(0,2),(1,3),(2,3),(3,4)]))  # True

import heapq
from collections import defaultdict

def topo_thu_tu_tu_dien(n, canh):
    """
    Sắp xếp tô pô theo thứ tự từ điển nhỏ nhất.
    Dùng min-heap thay vì thông thường queue.
    """
    graph  = defaultdict(list)
    in_deg = [0] * n
    for u, v in canh:
        graph[u].append(v)
        in_deg[v] += 1

    heap = [i for i in range(n) if in_deg[i] == 0]
    heapq.heapify(heap)
    result = []
    while heap:
        u = heapq.heappop(heap)
        result.append(u)
        for v in graph[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                heapq.heappush(heap, v)
    return result if len(result) == n else []

canh = [(0,2),(0,3),(1,4),(2,5),(3,5),(4,5)]
print("Thứ tự từ điển nhỏ nhất:", topo_thu_tu_tu_dien(6, canh))
# [0, 1, 2, 3, 4, 5]

from collections import defaultdict, deque

def duong_di_dai_nhat_dag(n, canh_trong_so):
    """
    Tìm đường đi dài nhất (theo trọng số) trong DAG.
    Dùng topo sort + DP.
    """
    graph  = defaultdict(list)
    in_deg = [0] * n
    for u, v, w in canh_trong_so:
        graph[u].append((v, w))
        in_deg[v] += 1

    # Bước 1: Topo sort (Kahn)
    q     = deque(i for i in range(n) if in_deg[i] == 0)
    order = []
    temp_in = in_deg[:]
    while q:
        u = q.popleft()
        order.append(u)
        for v, _ in graph[u]:
            temp_in[v] -= 1
            if temp_in[v] == 0:
                q.append(v)

    # Bước 2: DP theo thứ tự topo
    dist = [-float('inf')] * n
    for src in [i for i in range(n) if in_deg[i] == 0]:
        dist[src] = 0
    for u in order:
        if dist[u] == -float('inf'):
            continue
        for v, w in graph[u]:
            dist[v] = max(dist[v], dist[u] + w)
    return max(dist)

# DAG: 0→1(3), 0→2(6), 1→3(4), 2→3(2), 0→3(2)
canh = [(0,1,3),(0,2,6),(1,3,4),(2,3,2),(0,3,2)]
print("Đường đi dài nhất:", duong_di_dai_nhat_dag(4, canh))   # 8 (0→1→3)