Struct IndependentSubSet 

pub struct IndependentSubSet<M>
where
    M: MIntBase,
{
    pub n: usize,
    pub ind: Vec<MInt<M>>,
}

Fields

n: usize

ind: Vec<MInt<M>>

Implementations

impl<M> IndependentSubSet<M>

where M: MIntBase,

pub fn from_edges(n: usize, edges: &[(usize, usize)]) -> Self

Examples found in repository

crates/library_checker/src/graph/chromatic_number.rs (line 10)

pub fn chromatic_number(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, m, uv: [(usize, usize); m]);
    let ind = IndependentSubSet::<Modulo998244353>::from_edges(n, &uv);
    iter_print!(writer, ind.chromatic_number());
}

pub fn from_adj_graph(g: &[usize]) -> Self

Examples found in repository

crates/competitive/src/algorithm/chromatic_number.rs (line 22)

    pub fn from_edges(n: usize, edges: &[(usize, usize)]) -> Self {
        let mut g = vec![0; n];
        for &(u, v) in edges {
            g[u] |= 1 << v;
            g[v] |= 1 << u;
        }
        Self::from_adj_graph(&g)
    }

pub fn k_colorable(&self, k: usize) -> bool

Examples found in repository

crates/competitive/src/algorithm/chromatic_number.rs (line 49)

    pub fn chromatic_number(&self) -> usize {
        binary_search(|&k| self.k_colorable(k), self.n, 0)
    }

pub fn chromatic_number(&self) -> usize

The smallest number of colors needed to color a graph.

Examples found in repository

crates/library_checker/src/graph/chromatic_number.rs (line 11)

pub fn chromatic_number(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, m, uv: [(usize, usize); m]);
    let ind = IndependentSubSet::<Modulo998244353>::from_edges(n, &uv);
    iter_print!(writer, ind.chromatic_number());
}

Trait Implementations

impl<M> Clone for IndependentSubSet<M>

where M: MIntBase + Clone,

fn clone(&self) -> IndependentSubSet<M>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<M> Debug for IndependentSubSet<M>

where M: MIntBase + Debug,

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

Formats the value using the given formatter.