Function is_bipartite 

pub fn is_bipartite(g: &Graph) -> Option<Vec<u8>>

Graf ikki bo’lakli (bipartite) mi? — tugunlarni 2 rangga bo’yash mumkinmi, shundayki qo’shnilar har doim turli rangda bo’lsin.

Usul: BFS bilan yurib, har bir qavatni navbatma-navbat bo’yaymiz. Qo’shni bir xil rangga tushsa — bo’lmaydi.

Qayerda kerak: “ikki guruhga bo’lish”, “jadval to’qnashuvlari”, “toq uzunlikdagi sikl bormi?” masalalari.

Misol

use rust_algorithms::graph::{Graph, is_bipartite};

let mut kvadrat = Graph::new_undirected(4); // 4 uzunlikdagi sikl — juft
for (a, b) in [(0, 1), (1, 2), (2, 3), (3, 0)] {
    kvadrat.add_unweighted_edge(a, b);
}
assert!(is_bipartite(&kvadrat).is_some());

let mut uchburchak = Graph::new_undirected(3); // toq sikl
for (a, b) in [(0, 1), (1, 2), (2, 0)] {
    uchburchak.add_unweighted_edge(a, b);
}
assert!(is_bipartite(&uchburchak).is_none());