haar_lib/graph/
bipartite.rs

1//! 二部グラフ判定
2
3use crate::graph::*;
4
5/// 無向グラフが二部グラフであるかを判定する。
6///
7/// 連結成分ごとに、二部グラフならば`Some`に2つに分割された頂点集合を包んで、そうでなければ`None`を返す。
8pub fn check_bipartite<E: EdgeTrait>(
9    g: &Graph<Undirected, E>,
10) -> Vec<Option<(Vec<usize>, Vec<usize>)>> {
11    let n = g.len();
12    let mut ret = vec![];
13    let mut check = vec![-1; n];
14    let mut visit = vec![false; n];
15
16    for i in 0..n {
17        if visit[i] {
18            continue;
19        }
20
21        let mut a = vec![];
22        let mut b = vec![];
23
24        let res = (|| {
25            let mut stack = vec![i];
26            check[i] = 0;
27            a.push(i);
28
29            while let Some(cur) = stack.pop() {
30                if visit[cur] {
31                    continue;
32                }
33                visit[cur] = true;
34
35                for e in g.nodes[cur].edges.iter() {
36                    let to = e.to();
37                    if check[to] == check[cur] {
38                        return false;
39                    }
40                    if check[to] == -1 {
41                        if check[cur] == 0 {
42                            check[to] = 1;
43                            b.push(to);
44                        } else {
45                            check[to] = 0;
46                            a.push(to);
47                        }
48
49                        stack.push(to);
50                    }
51                }
52            }
53
54            true
55        })();
56
57        ret.push(res.then_some((a, b)));
58    }
59
60    ret
61}
haar_lib/graph/bipartite.rs

haar_lib/graph/
bipartite.rs
