haar_lib/graph/
enumerate_triangles.rs

1//! 無向グラフ上の3頂点で、各頂点間に辺のあるものを列挙する。
2//!
3//! # Problems
4//! - <https://judge.yosupo.jp/problem/enumerate_triangles>
5use crate::graph::*;
6use std::collections::HashSet;
7
8/// 無向グラフ上の3頂点で、各頂点間に辺のあるものを列挙する。
9pub fn enumerate_triangles<E: EdgeTrait>(g: &Graph<Undirected, E>) -> Vec<(usize, usize, usize)> {
10    let n = g.len();
11    let mut ret = vec![];
12    let mut adjacent = vec![HashSet::new(); n];
13
14    for e in g.nodes_iter().flat_map(|v| &v.edges) {
15        if g.nodes[e.from()].edges.len() < g.nodes[e.to()].edges.len()
16            || (g.nodes[e.from()].edges.len() == g.nodes[e.to()].edges.len() && e.from() < e.to())
17        {
18            adjacent[e.from()].insert(e.to());
19        }
20    }
21
22    for i in 0..n {
23        for &j in &adjacent[i] {
24            for &k in &adjacent[j] {
25                if adjacent[i].contains(&k) {
26                    ret.push((i, j, k));
27                }
28            }
29        }
30    }
31
32    ret
33}
haar_lib/graph/enumerate_triangles.rs

haar_lib/graph/
enumerate_triangles.rs
