dsalgo/
cycle_detection_undirected_graph_union_find.rs

1use crate::{
2    union_find_low_memory_with_trait::UnionFind,
3    union_find_traits::*,
4};
5
6pub fn has_cycle(
7    v_size: usize,
8    edges: &[(usize, usize)],
9) -> bool {
10    let mut uf = UnionFind::new(v_size);
11
12    for &(u, v) in edges.iter() {
13        if uf.same(u, v) {
14            return true;
15        }
16
17        uf.unite(u, v);
18    }
19
20    false
21}
22
23#[cfg(test)]
24
25mod tests {
26
27    use super::*;
28
29    #[test]
30
31    fn test() {
32        let cases = vec![
33            ((4, vec![(1, 0), (2, 0)]), false),
34            ((4, vec![(1, 0), (2, 0), (2, 1)]), true),
35        ];
36
37        for ((n, edges), ans) in cases {
38            assert_eq!(has_cycle(n, &edges), ans);
39        }
40    }
41}