ps:teflib:graph
목차
graph.py
imports and globals
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')
create_graph_from_input
코드
# 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
설명
- 그래프 참고
이 코드를 사용하는 문제
- 너무 많아서 생략
two_coloring
코드
# 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)
설명
- 2색 색칠 참고
이 코드를 사용하는 문제
출처 | 문제 번호 | Page | 레벨 |
---|---|---|---|
BOJ | 18282 | Golema Gozba | 다이아몬드 3 |
BOJ | 18929 | Knights of Round Table | 다이아몬드 3 |
BOJ | 1707 | 이분 그래프 | 골드 4 |
BOJ | 12893 | 적의 적 | 골드 4 |
minimum_spanning_tree
코드
# 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')
설명
이 코드를 사용하는 문제
minimum_spanning_tree_dense
코드
# 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))
설명
이 코드를 사용하는 문제
ps/teflib/graph.txt · 마지막으로 수정됨: 2023/04/04 14:58 저자 teferi
토론