Topological Sort

"""Topic  : Kahn's Algorithm — BFS-based Topological Sort
Time   : O(V + E)
Space  : O(V)"""

from collections import deque
import heapq


#── Kahn's Topological Sort ──────────────────────────────────────────────────────────

def kahns_sort(
    n: int, graph: list[list[int]]
) -> list[int] | None:
    """Topological sort using Kahn's algorithm.

    Returns:
        List of topological order, None if there is a cycle"""
    in_degree = [0] * (n + 1)
    for u in range(1, n + 1):
        for v in graph[u]:
            in_degree[v] += 1

    queue: deque[int] = deque(
        [i for i in range(1, n + 1) if in_degree[i] == 0]
    )
    result: list[int] = []

    while queue:
        node = queue.popleft()
        result.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)

    if len(result) < n:
        return None    #Cycle Exists

    return result


def kahns_sort_verbose(
    n: int, graph: list[list[int]]
) -> list[int] | None:
    """Step-by-step output of Kahn's algorithm."""
    in_degree = [0] * (n + 1)
    for u in range(1, n + 1):
        for v in graph[u]:
            in_degree[v] += 1

    print(f"Initial In-Degree: {in_degree[1:]}")

    queue: deque[int] = deque(
        [i for i in range(1, n + 1) if in_degree[i] == 0]
    )
    result: list[int] = []
    step = 0

    while queue:
        node = queue.popleft()
        result.append(node)
        step += 1
        updated = []
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            updated.append(nxt)
            if in_degree[nxt] == 0:
                queue.append(nxt)
        print(f"Step{step:2d}: pop={node},"
              f"In-Degree Decrease: {updated},"
              f"Queue: {list(queue)}")

    return result if len(result) == n else None


#── Lexicographically Minimum Topological Sort (using heapq) ───────────────────────────

def kahns_sort_lex(
    n: int, graph: list[list[int]]
) -> list[int] | None:
    """Lexicographically smallest topological sort (using heap)."""
    in_degree = [0] * (n + 1)
    for u in range(1, n + 1):
        for v in graph[u]:
            in_degree[v] += 1

    heap: list[int] = [i for i in range(1, n + 1) if in_degree[i] == 0]
    heapq.heapify(heap)
    result: list[int] = []

    while heap:
        node = heapq.heappop(heap)
        result.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                heapq.heappush(heap, nxt)

    return result if len(result) == n else None


#── Main ─────────────────────────────────────────────────────────────────────────

if __name__ == "__main__":
    #Construct DAG
    #  1 → 3 → 5
    #  2 → 3
    #  2 → 4 → 5
    n = 5
    edges = [(1, 3), (2, 3), (2, 4), (3, 5), (4, 5)]
    graph: list[list[int]] = [[] for _ in range(n + 1)]
    for u, v in edges:
        graph[u].append(v)

    print("=" * 55)
    print("Kahn's Topological Sort")
    print("=" * 55)
    result = kahns_sort_verbose(n, graph)
    print(f"\nTopological Sort Result: {result}")

    #Lexicographical Comparison
    print("\n=== Normal vs Lexicographical Minimum ===")
    result_lex = kahns_sort_lex(n, graph)
    print(f"Normal  : {result}")
    print(f"Lexicographical: {result_lex}")

    #Cycle Case
    print("\n=== Cycle Detection ===")
    n2 = 3
    g2: list[list[int]] = [[] for _ in range(n2 + 1)]
    for u, v in [(1, 2), (2, 3), (3, 1)]:
        g2[u].append(v)
    result2 = kahns_sort(n2, g2)
    print(f"Cycle Graph Result: {result2}  (None means cycle)")

    #Course Enrollment Example
    print("\n=== Course Enrollment Order ===")
    courses = {
        "Mathematics": 1, "Physics": 2, "Chemistry": 3,
        "Engineering Mathematics": 4, "Physics": 5, "Chemical Engineering": 6
    }
    prereqs = [
        (courses["Mathematics"], courses["Engineering Mathematics"]),
        (courses["Mathematics"], courses["Physics"]),
        (courses["Physics"], courses["Physics"]),
        (courses["Chemistry"], courses["Chemical Engineering"]),
        (courses["Engineering Mathematics"], courses["Chemical Engineering"]),
    ]
    n3 = len(courses)
    g3: list[list[int]] = [[] for _ in range(n3 + 1)]
    for u, v in prereqs:
        g3[u].append(v)
    order = kahns_sort(n3, g3)
    rev_courses = {v: k for k, v in courses.items()}
    if order:
        print(f"Enrollment Order: {[rev_courses[i] for i in order]}")

"""Topic  : DFS-based topological sort — reverse of post-order
Time   : O(V + E)
Space  : O(V) recursive stack"""

import sys
sys.setrecursionlimit(100_000)


#── DFS Topological Sort ─────────────────────────────────────────────────────────────

def dfs_topological_sort(
    n: int, graph: list[list[int]]
) -> list[int] | None:
    """DFS-based topological sort.

    The reverse of post-order is the topological order.

    Returns:
        Topological order, None if there is a cycle"""
    WHITE = 0   #Unvisited
    GRAY = 1    #Visiting (in DFS stack)
    BLACK = 2   #Fully Explored

    color = [WHITE] * (n + 1)
    post_order: list[int] = []
    has_cycle = [False]

    def dfs(node: int) -> None:
        color[node] = GRAY
        for nxt in graph[node]:
            if color[nxt] == GRAY:
                has_cycle[0] = True
                return
            if color[nxt] == WHITE:
                dfs(nxt)
                if has_cycle[0]:
                    return
        color[node] = BLACK
        post_order.append(node)

    for node in range(1, n + 1):
        if color[node] == WHITE:
            dfs(node)
            if has_cycle[0]:
                return None

    return post_order[::-1]


def dfs_topological_verbose(
    n: int, graph: list[list[int]]
) -> list[int] | None:
    """Step-by-step output of DFS topological sort."""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * (n + 1)
    post_order: list[int] = []
    has_cycle = [False]
    depth = [0]

    def dfs(node: int) -> None:
        color[node] = GRAY
        indent = "  " * depth[0]
        print(f"{indent}→ Enter node {node} (GRAY)")
        depth[0] += 1
        for nxt in graph[node]:
            if color[nxt] == GRAY:
                print(f"{indent}  ⚠ Cycle detected! {nxt} → {node}")
                has_cycle[0] = True
                return
            if color[nxt] == WHITE:
                dfs(nxt)
                if has_cycle[0]:
                    return
        depth[0] -= 1
        color[node] = BLACK
        post_order.append(node)
        print(f"{indent}← Node {node} completed (BLACK), post_order={post_order}")

    for node in range(1, n + 1):
        if color[node] == WHITE:
            dfs(node)
            if has_cycle[0]:
                return None

    result = post_order[::-1]
    print(f"\npost_order    : {post_order}")
    print(f"Topological sort order : {result}")
    return result


#── Main ─────────────────────────────────────────────────────────────────────────

if __name__ == "__main__":
    # DAG
    #  1 → 2 → 4
    #  1 → 3 → 4
    #         ↓
    #         5
    n = 5
    edges = [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]
    graph: list[list[int]] = [[] for _ in range(n + 1)]
    for u, v in edges:
        graph[u].append(v)

    print("=" * 55)
    print("DFS-based topological sort")
    print("=" * 55)
    result = dfs_topological_verbose(n, graph)

    #Compare with Kahn's
    from collections import deque

    def kahns(n: int, graph: list[list[int]]) -> list[int]:
        in_deg = [0] * (n + 1)
        for u in range(1, n + 1):
            for v in graph[u]:
                in_deg[v] += 1
        q: deque[int] = deque(i for i in range(1, n + 1) if in_deg[i] == 0)
        res: list[int] = []
        while q:
            node = q.popleft()
            res.append(node)
            for nxt in graph[node]:
                in_deg[nxt] -= 1
                if in_deg[nxt] == 0:
                    q.append(nxt)
        return res

    kahn_result = kahns(n, graph)
    print(f"Kahn's result  : {kahn_result}")
    print(f"DFS result      : {result}")

    #Validation (both results must be valid topological orders)
    def verify_topological(order: list[int], n: int, edges: list[tuple[int, int]]) -> bool:
        pos = {v: i for i, v in enumerate(order)}
        return all(pos[u] < pos[v] for u, v in edges)

    print(f"Kahn's validity: {verify_topological(kahn_result, n, edges)}")
    print(f"DFS validity   : {verify_topological(result or [], n, edges)")

    #Cycle Case
    print("\n=== Cycle Detection ===")
    n2 = 4
    g2: list[list[int]] = [[] for _ in range(n2 + 1)]
    for u, v in [(1, 2), (2, 3), (3, 4), (4, 2)]:  #Cycle 2→3→4→2
        g2[u].append(v)
    result2 = dfs_topological_sort(n2, g2)
    print(f"Cycle Graph Result: {result2}  (None means cycle)")

"""Topic  : Cycle Detection — Topological Sort Based (Directed Graph)
Time   : O(V + E)
Space  : O(V)"""

import sys
sys.setrecursionlimit(100_000)

from collections import deque


#── Kahn's Based Cycle Detection ──────────────────────────────────────────────────

def has_cycle_kahns(n: int, graph: list[list[int]]) -> bool:
    """Cycle detection in directed graphs using Kahn's algorithm.

    If the length of the topological sort result is less than V, a cycle exists."""
    in_degree = [0] * (n + 1)
    for u in range(1, n + 1):
        for v in graph[u]:
            in_degree[v] += 1

    queue: deque[int] = deque(
        i for i in range(1, n + 1) if in_degree[i] == 0
    )
    visited_count = 0

    while queue:
        node = queue.popleft()
        visited_count += 1
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)

    return visited_count < n


#── DFS Based Cycle Detection ─────────────────────────────────────────────────────

def has_cycle_dfs(n: int, graph: list[list[int]]) -> tuple[bool, list[int]]:
    """DFS-based cycle detection and returning the cycle path.

    Returns:
        (Whether a cycle exists, List of nodes in the cycle)"""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * (n + 1)
    parent = [-1] * (n + 1)
    cycle: list[int] = []

    def dfs(node: int) -> bool:
        color[node] = GRAY
        for nxt in graph[node]:
            if color[nxt] == GRAY:
                #Cycle Found — Reconstructing Path
                cycle.append(nxt)
                cur = node
                while cur != nxt:
                    cycle.append(cur)
                    cur = parent[cur]
                cycle.append(nxt)
                cycle.reverse()
                return True
            if color[nxt] == WHITE:
                parent[nxt] = node
                if dfs(nxt):
                    return True
        color[node] = BLACK
        return False

    for node in range(1, n + 1):
        if color[node] == WHITE:
            if dfs(node):
                return True, cycle

    return False, []


#── Examples of Graphs With/Without Cycles ─────────────────────────────────────────────

def demo_cycle_detection() -> None:
    """Cycle detection in various graphs."""
    test_cases = [
        #(n, edges, description)
        (4, [(1, 2), (2, 3), (3, 4)], "DAG (No Cycle)"),
        (4, [(1, 2), (2, 3), (3, 1)], "Triangle Cycle"),
        (5, [(1, 2), (2, 3), (3, 4), (4, 5), (5, 3)], "Long Cycle"),
        (4, [(1, 2), (1, 3), (2, 4), (3, 4)], "Diamond (No Cycle)"),
        (3, [(1, 1)], "Self Loop"),
    ]

    print("=== Cycle Detection Results ===")
    for n, edges, desc in test_cases:
        g: list[list[int]] = [[] for _ in range(n + 1)]
        for u, v in edges:
            g[u].append(v)

        has_c_k = has_cycle_kahns(n, g)
        has_c_d, cycle_path = has_cycle_dfs(n, g)

        print(f"\n{desc}:")
        print(f"Edges: {edges}")
        print(f"Kahn's: {'Cycle Exists' if has_c_k else 'No Cycle'}")
        print(f"DFS   : {'Cycle Exists' if has_c_d else 'No Cycle'}", end="")
        if cycle_path:
            print(f"Path: {' → '.join(map(str, cycle_path))}", end="")
        print()

        assert has_c_k == has_c_d, f"Algorithm Results Mismatch: {desc}"


#── Undirected Graph Cycle (DFS Based) ──────────────────────────────────────────

def has_cycle_undirected(
    n: int, graph: list[list[int]]
) -> bool:
    """Cycle detection in undirected graphs.

    Note: Different from directed graphs (excluding parent)"""
    visited = [False] * (n + 1)

    def dfs(node: int, parent: int) -> bool:
        visited[node] = True
        for nxt in graph[node]:
            if not visited[nxt]:
                if dfs(nxt, node):
                    return True
            elif nxt != parent:
                return True      #Node already visited but not the parent
        return False

    for node in range(1, n + 1):
        if not visited[node]:
            if dfs(node, -1):
                return True
    return False


#── Main ─────────────────────────────────────────────────────────────────────

if __name__ == "__main__":
    demo_cycle_detection()

    print("=== Undirected Graph Cycle Detection ===")
    #Triangle (Cycle Exists)
    n3 = 3
    g3: list[list[int]] = [[] for _ in range(n3 + 1)]
    for u, v in [(1, 2), (2, 3), (3, 1)]:
        g3[u].append(v)
        g3[v].append(u)
    print(f"Triangle: {has_cycle_undirected(n3, g3)}")

    #Tree (No Cycle)
    n4 = 4
    g4: list[list[int]] = [[] for _ in range(n4 + 1)]
    for u, v in [(1, 2), (1, 3), (2, 4)]:
        g4[u].append(v)
        g4[v].append(u)
    print(f"Tree  : {has_cycle_undirected(n4, g4)}")

"""Topic  : Determining and Applying Unique Topological Order
Time   : O(V + E)
Space  : O(V)"""

from collections import deque
import heapq


#── Determining Unique Topological Order ─────────────────────────────────────────────────────

def is_unique_topological(
    n: int, graph: list[list[int]]
) -> tuple[bool, list[int]]:
    """Determine if a topological sort is unique.

    In Kahn's algorithm, if there is always only one element in the queue, it is unique.

    Returns:
        (whether it is unique, topological order)"""
    in_degree = [0] * (n + 1)
    for u in range(1, n + 1):
        for v in graph[u]:
            in_degree[v] += 1

    queue: deque[int] = deque(
        i for i in range(1, n + 1) if in_degree[i] == 0
    )
    result: list[int] = []
    is_unique = True

    while queue:
        if len(queue) > 1:
            is_unique = False   #Two or more → choice occurs
        node = queue.popleft()
        result.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)

    if len(result) < n:
        return False, []   #Cycle

    return is_unique, result


#── Line Up Problem (Baekjoon 2252 Style) ────────────────────────────────────────

def lineup(
    n: int, conditions: list[tuple[int, int]]
) -> list[int] | None:
    """Order of lining up satisfying the conditions.

    conditions: (a, b) → a must be in front of b"""
    graph: list[list[int]] = [[] for _ in range(n + 1)]
    in_degree = [0] * (n + 1)

    for a, b in conditions:
        graph[a].append(b)
        in_degree[b] += 1

    queue: deque[int] = deque(
        i for i in range(1, n + 1) if in_degree[i] == 0
    )
    result: list[int] = []

    while queue:
        node = queue.popleft()
        result.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)

    return result if len(result) == n else None


#── Priority Queue Topological Sort (Baekjoon 1766 Style) ─────────────────────────────────

def priority_topological(
    n: int,
    graph: list[list[int]],
    priority: list[int],
) -> list[int] | None:
    """Priority-based topological sort.

    Once all prerequisite courses are completed, take courses with smaller numbers first."""
    in_degree = [0] * (n + 1)
    for u in range(1, n + 1):
        for v in graph[u]:
            in_degree[v] += 1

    heap: list[int] = [
        priority[i] for i in range(1, n + 1) if in_degree[i] == 0
    ]
    heapq.heapify(heap)
    result: list[int] = []

    #Mapping from priority → original node
    pri_to_node = {priority[i]: i for i in range(1, n + 1)}

    while heap:
        pri = heapq.heappop(heap)
        node = pri_to_node[pri]
        result.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                heapq.heappush(heap, priority[nxt])

    return result if len(result) == n else None


#── Main ─────────────────────────────────────────────────────────────────────

if __name__ == "__main__":
    print("=== Determining Unique Topological Order ===")

    #Unique case
    n1 = 5
    g1: list[list[int]] = [[] for _ in range(n1 + 1)]
    for u, v in [(1, 2), (2, 3), (3, 4), (4, 5)]:  #Linear
        g1[u].append(v)
    unique1, order1 = is_unique_topological(n1, g1)
    print(f"Linear graph: unique={unique1}, order={order1}")

    #Non-unique case
    n2 = 4
    g2: list[list[int]] = [[] for _ in range(n2 + 1)]
    for u, v in [(1, 3), (2, 3), (3, 4)]:  #1,2 order free
        g2[u].append(v)
    unique2, order2 = is_unique_topological(n2, g2)
    print(f"Branched graph: unique={unique2}, order={order2}")

    #Line up
    print("\n=== Line Up (Baekjoon 2252 Style) ===")
    n3, conditions = 3, [(1, 3), (2, 3)]
    result = lineup(n3, conditions)
    print(f"n=3, conditions={conditions}")
    print(f"Order: {result}")

    #Priority topological sort
    print("\n=== Priority Topological Sort (Baekjoon 1766 Style) ===")
    #4 problems: has prerequisite relations + solve smaller numbers first
    n4 = 4
    g4: list[list[int]] = [[] for _ in range(n4 + 1)]
    for u, v in [(4, 2), (3, 1)]:   #4→2, 3→1 (prerequisite relations)
        g4[u].append(v)
    #Use itself as priority (number = priority)
    pri = [0] + list(range(1, n4 + 1))   # pri[i] = i
    result4 = priority_topological(n4, g4, pri)
    print(f"Result: {result4}")
    print("Solve 3, 4 (no prerequisites) first, and smaller numbers take priority")

    #Verify accuracy
    assert unique1 is True
    assert unique2 is False
    print("Accuracy check: PASS")