Function detect_cycle::detect_cycle_undirected

pub fn detect_cycle_undirected(
    n: usize,
    edges: &[(usize, usize)]
) -> Option<Vec<usize>>

無向グラフの閉路を求めます。

• n: 頂点数
• edges: 辺

返り値は、閉路をなす辺の index のベクタです。

Example

use detect_cycle::detect_cycle_undirected;
//      0       1       3
// (0) --- (1) --- (2) --- (5)
//          |       |
//        5 |       | 2
//          |       |
//         (4) --- (3)
//              4

let cycle = detect_cycle_undirected(6, &[(0, 1), (1, 2), (2, 3), (2, 5), (3, 4), (4, 1)]).unwrap();
let candidates = vec![
    vec![1, 2, 4, 5],
    vec![2, 4, 5, 1],
    vec![4, 5, 1, 2],
    vec![5, 1, 2, 4],
    vec![1, 5, 4, 2],
    vec![5, 4, 2, 1],
    vec![4, 2, 1, 5],
    vec![2, 1, 5, 4],
];
assert!(candidates.contains(&cycle));