haar_lib/mul_graph/
mod.rs

1//! 頂点倍加グラフ
2//!
3//! # Problems
4//! - <https://atcoder.jp/contests/abc132/tasks/abc132_e>
5//! - <https://atcoder.jp/contests/wupc2012-closed/tasks/wupc2012_5>
6//! - <https://yukicoder.me/problems/no/807>
7//! - <https://atcoder.jp/contests/abc395/tasks/abc395_e>
8
9pub mod dijkstra;
10
11use std::collections::HashMap;
12use std::hash::Hash;
13
14/// [`MulGraph`]の辺
15#[derive(Clone, Debug)]
16pub struct Edge<V, W> {
17    /// 始点
18    pub from: V,
19    /// 終点
20    pub to: V,
21    /// 重み
22    pub weight: W,
23}
24
25impl<V, W> Edge<V, W> {
26    /// 始点`from`、終点`to`、重さ`weight`の辺を生成する。
27    pub fn new(from: V, to: V, weight: W) -> Self {
28        Self { from, to, weight }
29    }
30}
31
32/// 頂点倍加グラフ
33#[derive(Clone, Default, Debug)]
34pub struct MulGraph<V, W> {
35    nodes: HashMap<V, Vec<Edge<V, W>>>,
36}
37
38impl<V, W> MulGraph<V, W>
39where
40    V: Hash + Eq + Copy,
41    W: Copy,
42{
43    /// 空のグラフを作る。
44    pub fn new() -> Self {
45        Self {
46            nodes: HashMap::new(),
47        }
48    }
49
50    /// `u`,`v`間に双方向に辺を張る。
51    pub fn add_undirected(&mut self, u: V, v: V, weight: W) {
52        self.add_directed(u, v, weight);
53        self.add_directed(v, u, weight);
54    }
55
56    /// `from`から`to`への有向辺を張る。
57    pub fn add_directed(&mut self, from: V, to: V, weight: W) {
58        self.nodes
59            .entry(from)
60            .or_default()
61            .push(Edge::new(from, to, weight));
62    }
63
64    /// 頂点`cur`の隣接辺への参照へのイテレータを返す。
65    pub fn neighbours_of(&self, cur: V) -> impl Iterator<Item = &Edge<V, W>> {
66        self.nodes.get(&cur).into_iter().flatten()
67    }
68}
haar_lib/mul_graph/mod.rs

haar_lib/mul_graph/
mod.rs
