"""
Depth-First Search — MAT5EJ302(1) Module II & III
DFS on undirected and directed graphs with pre/post times.
Includes: connectivity check, cycle detection, component finding.
"""

import sys
sys.setrecursionlimit(10000)


def dfs(graph):
    """
    DFS on a graph (directed or undirected).
    Records pre-visit and post-visit times for all vertices.

    Args:
        graph: dict mapping vertex -> list of neighbours

    Returns:
        pre:     dict[vertex] -> pre-visit time
        post:    dict[vertex] -> post-visit time
        tree:    dict[vertex] -> parent in DFS tree (None if root)
        components: list of sets, each set is one DFS tree
    """
    visited = set()
    pre = {}
    post = {}
    tree = {}
    clock = [1]
    components = []

    def explore(v, parent):
        visited.add(v)
        pre[v] = clock[0]; clock[0] += 1
        tree[v] = parent

        for u in graph.get(v, []):
            if u not in visited:
                explore(u, v)

        post[v] = clock[0]; clock[0] += 1

    for v in graph:
        if v not in visited:
            comp_before = set(visited)
            explore(v, None)
            comp = set(visited) - comp_before
            comp.add(v)
            components.append(frozenset(comp))

    return pre, post, tree, components


def has_cycle_directed(graph):
    """
    Detect cycle in a directed graph using DFS.
    A directed graph has a cycle iff DFS finds a back edge
    (edge to a vertex currently on the DFS stack).
    """
    visited = set()
    on_stack = set()    # currently in DFS recursion stack

    def dfs_visit(v):
        visited.add(v)
        on_stack.add(v)
        for u in graph.get(v, []):
            if u not in visited:
                if dfs_visit(u):
                    return True    # cycle found deeper
            elif u in on_stack:
                return True        # back edge found!
        on_stack.remove(v)
        return False

    for v in graph:
        if v not in visited:
            if dfs_visit(v):
                return True
    return False


def is_connected_undirected(graph):
    """Check if an undirected graph is connected."""
    if not graph:
        return True
    start = next(iter(graph))
    visited = set()

    def explore(v):
        visited.add(v)
        for u in graph.get(v, []):
            if u not in visited:
                explore(u)

    explore(start)
    return len(visited) == len(graph)


def topological_sort(graph):
    """
    Topological sort of a DAG using DFS post-order (reversed).
    Returns a list of vertices in topological order.
    Raises ValueError if the graph has a cycle.
    """
    if has_cycle_directed(graph):
        raise ValueError("Graph has a cycle — topological sort not possible.")

    visited = set()
    order = []

    def explore(v):
        visited.add(v)
        for u in graph.get(v, []):
            if u not in visited:
                explore(u)
        order.append(v)   # post-order

    for v in graph:
        if v not in visited:
            explore(v)

    return list(reversed(order))


if __name__ == "__main__":
    print("=== DFS on Undirected Graph ===")
    undirected = {
        'A': ['B', 'C'],
        'B': ['A', 'D'],
        'C': ['A', 'D'],
        'D': ['B', 'C', 'E'],
        'E': ['D']
    }

    pre, post, tree, comps = dfs(undirected)
    print(f"{'Vertex':>8}  {'pre':>5}  {'post':>5}  {'parent':>8}")
    for v in sorted(pre):
        p = tree[v] if tree[v] is not None else "—"
        print(f"{v:>8}  {pre[v]:>5}  {post[v]:>5}  {p:>8}")

    print(f"\nConnected: {is_connected_undirected(undirected)}")

    print()
    print("=== DFS on Directed Graph ===")
    directed = {
        1: [2, 4],
        2: [3],
        3: [1],     # back edge 3→1 creates cycle
        4: [5],
        5: [4]      # back edge 5→4 creates cycle
    }
    pre, post, tree, comps = dfs(directed)
    print(f"{'Vertex':>8}  {'pre':>5}  {'post':>5}")
    for v in sorted(pre):
        print(f"{v:>8}  {pre[v]:>5}  {post[v]:>5}")
    print(f"\nHas cycle: {has_cycle_directed(directed)}")

    print()
    print("=== Disconnected Graph — Components ===")
    disc = {
        'A': ['B'], 'B': ['A'],
        'C': ['D'], 'D': ['C', 'E'], 'E': ['D'],
        'F': []
    }
    _, _, _, components = dfs(disc)
    for i, comp in enumerate(components, 1):
        print(f"  Component {i}: {sorted(comp)}")

    print()
    print("=== Topological Sort on DAG ===")
    dag = {
        'Calculus': ['ODE', 'LinAlg'],
        'ODE':      ['Numerical'],
        'LinAlg':   ['Numerical'],
        'Numerical': [],
    }
    order = topological_sort(dag)
    print("  Topological order:", " → ".join(order))