Graph Representation

"""Topic  : Adjacency List — dict and list-of-lists, directed/undirected
Time   : O(V + E) time
Space  : O(V + E)"""

from collections import defaultdict


#── List-based Adjacency List ───────────────────────────────────────────────────

def build_undirected_list(n: int, edges: list[tuple[int, int]]) -> list[list[int]]:
    """Undirected graph adjacency list (1-indexed).

    Args:
        n: number of nodes (1~n)
        edges: list of (u, v) pairs"""
    graph: list[list[int]] = [[] for _ in range(n + 1)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)    #Add Both Directions
    return graph


def build_directed_list(n: int, edges: list[tuple[int, int]]) -> list[list[int]]:
    """Directed graph adjacency list (1-indexed)."""
    graph: list[list[int]] = [[] for _ in range(n + 1)]
    for u, v in edges:
        graph[u].append(v)    #Only u → v Direction
    return graph


#── Dictionary-based Adjacency List ────────────────────────────────────────────────

def build_graph_dict(
    edges: list[tuple[int, int]],
    directed: bool = False,
) -> dict[int, list[int]]:
    """Adjacency list based on defaultdict.

    Useful when node numbers are discontinuous or strings."""
    graph: dict[int, list[int]] = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        if not directed:
            graph[v].append(u)
    return dict(graph)


#── Output ─────────────────────────────────────────────────────────────────────

def print_graph(graph: list[list[int]], title: str = "Graph") -> None:
    """Print adjacency list."""
    print(f"\n=== {title} ===")
    for i, neighbors in enumerate(graph):
        if i == 0:
            continue    #Skipping 0 because it is 1-indexed
        print(f"  {i}: {neighbors}")


def print_graph_dict(
    graph: dict[int, list[int]], title: str = "Graph"
) -> None:
    """Print dictionary-based adjacency list."""
    print(f"\n=== {title} ===")
    for node in sorted(graph):
        print(f"  {node}: {sorted(graph[node])}")


#── Graph Information ───────────────────────────────────────────────────────────────

def graph_info(graph: list[list[int]]) -> None:
    """Print basic graph information."""
    n = len(graph) - 1
    edge_count = sum(len(adj) for adj in graph[1:])
    print(f"Number of Nodes: {n}")
    print(f"Number of Edges (Direction-based): {edge_count}")
    degrees = [len(graph[i]) for i in range(1, n + 1)]
    print(f"Maximum Degree: {max(degrees)}, Minimum Degree: {min(degrees)}")


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

if __name__ == "__main__":
    #Example Undirected Graph
    #    1 --- 2
    #    |     |
    #    3 --- 4 --- 5
    n = 5
    undirected_edges = [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]

    g_und = build_undirected_list(n, undirected_edges)
    print_graph(g_und, "Undirected Graph")
    print("Information:")
    graph_info(g_und)

    #Directed Graph
    #    1 → 2 → 4
    #    ↓       ↑
    #    3 ──────┘
    directed_edges = [(1, 2), (1, 3), (2, 4), (3, 4)]
    g_dir = build_directed_list(n, directed_edges)
    print_graph(g_dir, "Directed Graph")
    print("Information:")
    graph_info(g_dir)

    #Dictionary Method (String Nodes)
    str_edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D")]
    g_str: dict[str, list[str]] = defaultdict(list)
    for u, v in str_edges:
        g_str[u].append(v)
        g_str[v].append(u)
    print("\n=== String Node Graph ===")
    for node in sorted(g_str):
        print(f"  {node}: {sorted(g_str[node])}")

    #Check Space Complexity
    print("\n=== Space Complexity Comparison ===")
    for v, e in [(10, 15), (100, 200), (1000, 3000)]:
        list_size = v + e      # O(V + E)
        matrix_size = v * v    # O(V²)
        print(f"V={v:>5}, E={e:>5}: "
              f"Adjacency List O({list_size:>7,}),"
              f"Adjacency Matrix O({matrix_size:>10,})")

"""Topic  : Adjacency Matrix — Space Analysis, Suitable Use Cases
Time   : O(V²) Time
Space  : O(V²)"""


#── Building Adjacency Matrix ────────────────────────────────────────────

def build_matrix_undirected(
    n: int, edges: list[tuple[int, int]]
) -> list[list[int]]:
    """Undirected Graph Adjacency Matrix (1-indexed).

    matrix[i][j] = 1 if an edge exists between i and j."""
    matrix = [[0] * (n + 1) for _ in range(n + 1)]
    for u, v in edges:
        matrix[u][v] = 1
        matrix[v][u] = 1
    return matrix


def build_matrix_directed(
    n: int, edges: list[tuple[int, int]]
) -> list[list[int]]:
    """Directed Graph Adjacency Matrix."""
    matrix = [[0] * (n + 1) for _ in range(n + 1)]
    for u, v in edges:
        matrix[u][v] = 1
    return matrix


def build_matrix_weighted(
    n: int,
    edges: list[tuple[int, int, int]],
    directed: bool = False,
    no_edge: int | float = 0,
) -> list[list[int | float]]:
    """Weighted Graph Adjacency Matrix.

    Args:
        no_edge: Value if there is no edge (0 or float('inf'))"""
    matrix: list[list[int | float]] = [
        [no_edge] * (n + 1) for _ in range(n + 1)
    ]
    for u, v, w in edges:
        matrix[u][v] = w
        if not directed:
            matrix[v][u] = w
    return matrix


#── Output ─────────────────────────────────────────────────────────────────────

def print_matrix(
    matrix: list[list[int | float]], n: int, title: str = "Adjacency Matrix"
) -> None:
    """Print Adjacency Matrix."""
    print(f"\n=== {title} ===")
    #Header
    header = "   " + " ".join(f"{j:3d}" for j in range(1, n + 1))
    print(header)
    print("   " + "----" * n)
    for i in range(1, n + 1):
        row_vals = []
        for j in range(1, n + 1):
            v = matrix[i][j]
            if v == float('inf'):
                row_vals.append("  ∞")
            else:
                row_vals.append(f"{v:3g}")
        print(f"{i:2d}|" + " ".join(row_vals))


#── Edge Lookup O(1) ────────────────────────────────────────────────

def has_edge(
    matrix: list[list[int | float]], u: int, v: int
) -> bool:
    """Check edge existence in O(1)."""
    return matrix[u][v] != 0


def get_neighbors(
    matrix: list[list[int | float]], u: int, n: int
) -> list[int]:
    """List of u's adjacent nodes (O(V))."""
    return [v for v in range(1, n + 1) if matrix[u][v] != 0]


#── Space Analysis ─────────────────────────────────────────────────

def space_analysis() -> None:
    """Analyze adjacency matrix space usage."""
    print("=== Space Usage Analysis ===")
    print("(Python int = 28 bytes, excluding list overhead)")
    print(f"{'V':>6}  {'V²':>10}  {'Memory (MB)':>12}")
    for v in [10, 100, 500, 1000, 5000, 10000]:
        cells = v * v
        mb = cells * 28 / 1024 / 1024
        feasible = "✅" if mb < 256 else "❌"
        print(f"{v:>6}  {cells:>10,}  {mb:>10.1f}MB  {feasible}")


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

if __name__ == "__main__":
    #Undirected Graph
    n = 5
    edges = [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]

    mat = build_matrix_undirected(n, edges)
    print_matrix(mat, n, "Undirected Adjacency Matrix")

    print(f"Does edge 1-2 exist? {has_edge(mat, 1, 2)}")
    print(f"Does edge 1-4 exist? {has_edge(mat, 1, 4)}")
    print(f"Neighbors of node 1: {get_neighbors(mat, 1, n)}")
    print(f"Neighbors of node 4: {get_neighbors(mat, 4, n)}")

    #Weighted Directed Graph
    INF = float('inf')
    weighted_edges = [(1, 2, 5), (1, 3, 3), (2, 4, 7), (3, 4, 2)]
    wmat = build_matrix_weighted(n, weighted_edges, directed=True, no_edge=INF)
    #Self is 0
    for i in range(1, n + 1):
        wmat[i][i] = 0
    print_matrix(wmat, n, "Weighted Directed Adjacency Matrix (∞ = none)")

    space_analysis()

    print("=== Adjacency Matrix vs Adjacency List Selection Criteria ===")
    criteria = [
        ("V ≤ 1000 and E ≈ V² (dense)", "Adjacency Matrix"),
        ("Frequent O(1) lookup of specific edges", "Adjacency Matrix"),
        ("Floyd-Warshall Algorithm", "Adjacency Matrix"),
        ("V is large or E << V² (sparse)", "Adjacency list"),
        ("General search like DFS/BFS", "Adjacency list"),
    ]
    for cond, choice in criteria:
        print(f"  {cond:45s} → {choice}")

"""Topic: Weighted Graph Representation — Adjacency List and Edge Representation
Time: O(V + E)
Space: O(V + E)"""

from collections import defaultdict
from dataclasses import dataclass


#── Weighted Adjacency List (Tuple) ─────────────────────────────────────────────

def build_weighted_list(
    n: int,
    edges: list[tuple[int, int, int]],
    directed: bool = False,
) -> list[list[tuple[int, int]]]:
    """Weighted graph adjacency list.

    graph[u] = [(v, weight), ...]"""
    graph: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    for u, v, w in edges:
        graph[u].append((v, w))
        if not directed:
            graph[v].append((u, w))
    return graph


#── Edge Class ─────────────────────────────────────────────────────────────────

@dataclass
class Edge:
    u: int
    v: int
    weight: int

    def __repr__(self) -> str:
        return f"Edge({self.u}→{self.v}, w={self.weight})"

    def reversed(self) -> "Edge":
        return Edge(self.v, self.u, self.weight)


def build_edge_list(
    edges_raw: list[tuple[int, int, int]]
) -> list[Edge]:
    """List of Edge objects."""
    return [Edge(u, v, w) for u, v, w in edges_raw]


#── Edge-Based Adjacency List ─────────────────────────────────────────────────

def build_graph_from_edges(
    n: int, edge_list: list[Edge], directed: bool = False
) -> dict[int, list[Edge]]:
    """Adjacency list using Edge objects."""
    graph: dict[int, list[Edge]] = defaultdict(list)
    for edge in edge_list:
        graph[edge.u].append(edge)
        if not directed:
            graph[edge.v].append(edge.reversed())
    return dict(graph)


#── Output ───────────────────────────────────────────────────────────────────

def print_weighted_graph(
    graph: list[list[tuple[int, int]]],
    title: str = "Weighted Graph",
) -> None:
    """Print weighted adjacency list."""
    print(f"\n=== {title} ===")
    for i in range(1, len(graph)):
        if graph[i]:
            neighbors = ", ".join(f"{v}(w={w})" for v, w in graph[i])
            print(f"  {i}: [{neighbors}]")


#── Statistics ────────────────────────────────────────────────────────────────

def graph_stats(
    graph: list[list[tuple[int, int]]]
) -> None:
    """Weighted graph statistics."""
    n = len(graph) - 1
    all_weights = [w for adj in graph[1:] for _, w in adj]
    if not all_weights:
        return
    print(f"Number of Nodes: {n}")
    print(f"Number of Edges (Directed Basis): {len(all_weights)}")
    print(f"Minimum Weight: {min(all_weights)}")
    print(f"Maximum Weight: {max(all_weights)}")
    print(f"Average Weight: {sum(all_weights)/len(all_weights):.1f}")


#── Dijkstra Preparation Check ──────────────────────────────────────────────────

def check_negative_weights(
    graph: list[list[tuple[int, int]]]
) -> bool:
    """Check for negative weights (whether Dijkstra can be used)."""
    for adj in graph[1:]:
        for _, w in adj:
            if w < 0:
                return True
    return False


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

if __name__ == "__main__":
    #Weighted Undirected Graph
    #  1 --5-- 2
    #  |       |
    #  3       7
    #  |
    #  1 --2-- 3 --1-- 4
    n = 5
    weighted_edges = [
        (1, 2, 5),
        (1, 3, 3),
        (2, 4, 7),
        (3, 4, 2),
        (3, 5, 8),
        (4, 5, 1),
    ]

    g = build_weighted_list(n, weighted_edges)
    print_weighted_graph(g, "Weighted Undirected Graph")
    print("Statistics:")
    graph_stats(g)
    print(f"Has negative weights? {check_negative_weights(g)}")

    #Weighted Directed Graph
    directed_weighted = [
        (1, 2, 10),
        (1, 3, 3),
        (2, 4, 2),
        (3, 2, 4),
        (3, 4, 8),
        (4, 5, 5),
    ]
    g_dir = build_weighted_list(n, directed_weighted, directed=True)
    print_weighted_graph(g_dir, "Weighted Directed Graph")

    #Using Edge Object
    print("=== Edge Object Method ===")
    edges = build_edge_list(weighted_edges)
    g_edge = build_graph_from_edges(n, edges)
    for node in sorted(g_edge):
        print(f"  {node}: {[str(e) for e in g_edge[node]]}")

    #Typical Dijkstra Code Pattern
    print("=== Dijkstra Preparation Pattern ===")
    print("import heapq")
    print("dist = [float('inf')] * (n + 1)")
    print("dist[start] = 0")
    print("heap = [(0, start)]  # (distance, node)")
    print("while heap:")
    print("    d, u = heapq.heappop(heap)")
    print("    for v, w in graph[u]:")
    print("        if dist[u] + w < dist[v]:")
    print("            dist[v] = dist[u] + w")
    print("            heapq.heappush(heap, (dist[v], v))")

"""Topic  : Parsing Baekjoon-style graph input
Time   : O(V + E)
Space  : O(V + E)

Typical input format for Baekjoon graph problems:
First line: N M (number of nodes, number of edges)
Next M lines: u v [w] (edge information)"""

import sys
from io import StringIO


#── Typical Baekjoon input parsing ─────────────────────────────────────────────

def parse_unweighted_graph(data: str, directed: bool = False) -> tuple[int, list[list[int]]]:
    """Parsing an unweighted graph.

    Input format:
      First line: N M
      Next M lines: u v"""
    tokens = data.split()
    idx = 0
    n = int(tokens[idx]); idx += 1
    m = int(tokens[idx]); idx += 1

    graph: list[list[int]] = [[] for _ in range(n + 1)]
    for _ in range(m):
        u = int(tokens[idx]); idx += 1
        v = int(tokens[idx]); idx += 1
        graph[u].append(v)
        if not directed:
            graph[v].append(u)

    return n, graph


def parse_weighted_graph(
    data: str, directed: bool = False
) -> tuple[int, list[list[tuple[int, int]]]]:
    """Parsing a weighted graph.

    Input format:
      First line: N M
      Next M lines: u v w"""
    tokens = data.split()
    idx = 0
    n = int(tokens[idx]); idx += 1
    m = int(tokens[idx]); idx += 1

    graph: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    for _ in range(m):
        u = int(tokens[idx]); idx += 1
        v = int(tokens[idx]); idx += 1
        w = int(tokens[idx]); idx += 1
        graph[u].append((v, w))
        if not directed:
            graph[v].append((u, w))

    return n, graph


#── Grid graph parsing ─────────────────────────────────────────────────────────

def parse_grid(data: str) -> list[list[str]]:
    """Parsing an NxM grid.

    Input format:
      First line: N M
      Next N lines: each row (string without spaces or space-separated)"""
    lines = data.strip().split('\n')
    n, m = map(int, lines[0].split())
    grid = []
    for i in range(1, n + 1):
        row = list(lines[i].strip())
        grid.append(row)
    return grid


def grid_to_graph(
    grid: list[list[str]],
    passable: str = '0',
) -> tuple[int, int, list[list[tuple[int, int]]]]:
    """Converting a grid to a graph (4 directions).

    Returns:
        (rows, cols, graph)  accessed via graph[(r,c)]"""
    rows = len(grid)
    cols = len(grid[0])
    #(r, c) → Node number: r*cols + c
    total = rows * cols
    graph: list[list[tuple[int, int]]] = [[] for _ in range(total)]

    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != passable:
                continue
            node = r * cols + c
            for d in range(4):
                nr, nc = r + dr[d], c + dc[d]
                if 0 <= nr < rows and 0 <= nc < cols:
                    if grid[nr][nc] == passable:
                        nnode = nr * cols + nc
                        graph[node].append((nnode, 1))

    return rows, cols, graph


#── Demo ─────────────────────────────────────────────────────────────────────

def demo_parse() -> None:
    #Baekjoon 1260 style input
    input1 = """4 5 1
1 2
1 3
1 4
2 4
3 4"""
    tokens = input1.split()
    n, m, start = int(tokens[0]), int(tokens[1]), int(tokens[2])
    data_for_parse = f"{n} {m}\n" + '\n'.join(
        tokens[3:3 + m * 2][i*2] + ' ' + tokens[3:3 + m * 2][i*2 + 1]
        for i in range(m)
    )

    n2, graph = parse_unweighted_graph(data_for_parse)
    print(f"=== Unweighted graph parsing ===")
    print(f"N={n2}, Start={start}")
    for i in range(1, n2 + 1):
        print(f"  {i}: {sorted(graph[i])}")

    #Weighted graph
    input2 = """5 6
1 2 10
1 3 3
2 4 7
3 2 4
3 4 8
4 5 5"""
    n3, wgraph = parse_weighted_graph(input2, directed=True)
    print(f"\n=== Weighted directed graph parsing ===")
    print(f"N={n3}")
    for i in range(1, n3 + 1):
        if wgraph[i]:
            print(f"  {i}: {wgraph[i]}")

    #Grid
    input3 = """4 6
101110
101010
111010
000010"""
    grid = parse_grid(input3)
    print(f"\n=== Grid parsing ===")
    for row in grid:
        print(f"  {''.join(row)}")

    rows, cols, ggraph = grid_to_graph(grid, passable='1')
    passable_count = sum(1 for row in grid for c in row if c == '1')
    print(f"Passable cells: {passable_count}")


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

if __name__ == "__main__":
    demo_parse()

    #General pattern output when entering edges
    print("\n=== Common pattern for Baekjoon graph problems ===")
    print("""# Standard pattern
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]  # 1-indexed

for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)  # if undirected""")