Topological Sort — அடிப்படை

Topological Sort — வரைபடத்தில் முக்கியமான நுட்பம்.

உண்மை உலகில் இது ஏன் முக்கியம்?

வரைபடம், சமூக வலை, சார்பு அமைப்பு — தலைகோடுகள்/விளிம்புகள் மாதிரி.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

Kahn indegree 0; DFS முடிவு வரிசை.

Pythonில் முயற்சி செய்வோம்

from collections import deque


def topo_sort(n: int, edges: list[tuple[int, int]]) -> list[int]:
    indeg = [0] * n
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order: list[int] = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else []


print(topo_sort(4, [(0, 1), (0, 2), (1, 3), (2, 3)]))

பொதுவான தவறுகள்

• சுழற்சி DAG இல்லை.
• indegree தவறு.

முக்கிய பாடங்கள்

• DAG நீளம்=DP.
• முக்கிய பாதை.