====== graph.py ======

===== imports and globals =====
<dkpr py>
import collections
from collections.abc import (
    Callable,
    Collection,
    Iterable,
    Mapping,
    MutableSequence,
    Sequence,
)
import heapq
import itertools
import operator
import sys
from typing import cast, Literal, TypeAlias

from teflib import disjointset

Node: TypeAlias = int
Graph: TypeAlias = Sequence[Iterable[int]]
WGraph: TypeAlias = Sequence[Mapping[int, float]]
EdgeGraph: TypeAlias = list[tuple[int, int]]
EdgeDiGraph: TypeAlias = list[tuple[int, int]]
EdgeWGraph: TypeAlias = list[tuple[int, int, float]]
MatGraph: TypeAlias = Sequence[Sequence[float]]

INF = float('inf')
</dkpr>


===== create_graph_from_input =====

==== 코드 ====
<dkpr py>
# N create_graph_from_input
# I {"version": "0.1"}
def create_graph_from_input(
    node_count: int,
    edge_count: int,
    *,
    input_func: Callable[[], str] | None = None,
    is_undirected=True,
    base: Literal[0, 1] = 1,
) -> list[list[Node]]:
    """Create an undirected graph by reading edges from stdin."""
    input_func = input_func or sys.stdin.readline
    graph: list[list[Node]] = [[] for _ in range(node_count)]
    for _ in range(edge_count):
        u, v = [int(x) - base for x in input_func().split()]
        graph[u].append(v)
        if is_undirected:
            graph[v].append(u)
    return graph
</dkpr>

==== 설명 ====
  * [[ps:그래프]] 참고

==== 이 코드를 사용하는 문제 ====
  * 너무 많아서 생략




===== two_coloring =====

==== 코드 ====
<dkpr py>
# N two_coloring
# I {"version": "0.3"}
def two_coloring(graph: Graph) -> list[bool]:
    """Find 2-coloring of graph in O(|V|+|E|).

    Note that a graph is 2-colorable iff it's bipartite.

    Args:
        graph: An undirected graph.

    Returns:
        A list mapping nodes to color represented as boolean (True or False).

    Raises:
        ValueError: If the graph is not 2-colorable (= not bipartite).
    """
    color: list[bool | None] = [None] * len(graph)
    for source, col in enumerate(color):
        if col is not None:
            continue
        color[source] = True
        stack = [source]
        while stack:
            u = stack.pop()
            col_u = color[u]
            for v in graph[u]:
                if color[v] is None:
                    color[v] = not col_u
                    stack.append(v)
                elif color[v] == col_u:
                    raise ValueError('Graph is not 2-colorable.')
    return cast(list[bool], color)

</dkpr>

==== 설명 ====
  * [[ps:2색 색칠]] 참고

==== 이 코드를 사용하는 문제 ====
---- struct table ----
schema: ps
cols: site, prob_id, %title%, prob_level
filter: teflib ~ *[graph.two_coloring]*
csv: 0
----




===== minimum_spanning_tree =====

==== 코드 ====
<dkpr py>
# N minimum_spanning_tree
# I {"version": "1.01", "import": ["operator"], "func": ["disjointset.DisjointSet"], "const": ["INF", "EdgeWGraph"]}
def minimum_spanning_tree(graph_edges: EdgeWGraph,
                          node_count: int) -> EdgeWGraph:
    """Returns the minimum spanning tree of given graph."""
    dsu = disjointset.DisjointSet(node_count)
    component_count, mst_edges = node_count, []
    for e in sorted(graph_edges, key=operator.itemgetter(2)):
        u, v, _ = e
        if dsu.union_if_disjoint(u, v):
            mst_edges.append(e)
            component_count -= 1
            if component_count == 1:
                return mst_edges
    raise ValueError('Graph is not connected')
</dkpr>

==== 설명 ====
  * [[ps:최소 신장 트리]] 참고

==== 이 코드를 사용하는 문제 ====
---- struct table ----
schema: ps
cols: site, prob_id, %title%, prob_level
filter: teflib ~ *[graph.minimum_spanning_tree]*
csv: 0
----




===== minimum_spanning_tree_dense =====

==== 코드 ====
<dkpr py>
# N minimum_spanning_tree_dense
# I {"version": "1.1", "import": ["operator"], "const": ["EdgeWGraph", "MatGraph", "INF"]}
def minimum_spanning_tree_dense(mat_graph) -> EdgeWGraph:
    """Returns MST of given complete undirected graph.

    Implementation is based on Prim's algorithm, running in O(V^2)."""
    weights = {x: INF for x in range(1, len(mat_graph))}
    par = [None] * len(mat_graph)
    min_weight_node = 0
    mst_edges = []
    for _ in range(len(mat_graph) - 1):
        p = min_weight_node
        weights_from_p = mat_graph[p]
        min_weight = INF
        for v, weight_v in weights.items():
            if (w := weights_from_p[v]) < weight_v:
                par[v], weights[v], weight_v = p, w, w
            if weight_v < min_weight:
                min_weight_node, min_weight = v, weight_v
        mst_edges.append((par[min_weight_node], min_weight_node, min_weight))
        del weights[min_weight_node]
    return sorted(mst_edges, key=operator.itemgetter(2))
</dkpr>

==== 설명 ====
  * [[ps:최소 신장 트리]] 참고

==== 이 코드를 사용하는 문제 ====
---- struct table ----
schema: ps
cols: site, prob_id, %title%, prob_level
filter: teflib ~ *[graph.minimum_spanning_tree_dense]*
csv: 0
----