Struct cp_library_rs::graph::simple_graph::SimpleGraph

pub struct SimpleGraph {
    pub V: usize,
    pub E: usize,
    pub graph: Vec<Vec<usize>>,
    pub edges: Vec<(usize, usize)>,
    pub component_size: Option<usize>,
    pub components: Vec<usize>,
}

単純グラフ

単純グラフに対して

• 連結成分分解
• 2部グラフ分解

を行う。

Fields

V: usize

E: usize

graph: Vec<Vec<usize>>

edges: Vec<(usize, usize)>

component_size: Option<usize>

components: Vec<usize>

Implementations

impl SimpleGraph

pub fn new(V: usize) -> Self

グラフの構築

pub fn add_edge(&mut self, u: usize, v: usize)

辺の追加

pub fn decompose(&mut self)

連結成分に分解：O(|V|+|E|)

pub fn bipartite(&mut self) -> Option<Vec<isize>>

2部グラフ判定：O(|V|+|E|)

Trait Implementations

impl Debug for SimpleGraph

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.