fork download
  1. use std::collections::{BTreeSet, HashMap};
  2. fn f<'a>(a: &[&'a str]) -> Vec<Vec<&'a str>> { // '
  3. fn g(mut a: Vec<BTreeSet<usize>>) -> Vec<BTreeSet<usize>> {
  4. let comb = |n| (0..n).flat_map(move |i| (i + 1..n).map(move |j| (i, j)));
  5. match comb(a.len()).find(|&(i, j)| !a[i].is_disjoint(&a[j])) {
  6. None => a,
  7. Some((i, j)) => {
  8. let js = a.remove(j);
  9. a[i].extend(js);
  10. g(a)
  11. },
  12. }
  13. }
  14. let h = a.iter().map(|&s| s.split('=')).flatten().rev().enumerate().map(|(p, s)| (s, a.len() * 2 - p)).collect::<HashMap<_, _>>();
  15. let a = a.iter().map(|&s| s.split('=').flat_map(|k| h.get(k)).cloned().collect::<BTreeSet<_>>()).collect();
  16. let hi = h.iter().map(|(&k, &v)| (v, k)).collect::<HashMap<_, _>>();
  17. g(a).iter().map(|set| set.iter().flat_map(|i| hi.get(i)).cloned().collect()).collect()
  18. }
  19. fn main() {
  20. let v = ["a1=a2", "b1=b2", "b3=b2", "c1=c2", "e1=e2",
  21. "a3=a4", "c3=c4", "e1=e3", "a2=a4", "c3=c1",
  22. "b3=a4", "c2=d1", "a4=a5", "d2=c1", "b4=b3", "d3=c3"];
  23. println!("{:?}", f(&v));
  24. }
Success #stdin #stdout 0s 5292KB
stdin
Standard input is empty
stdout
[["a1", "a2", "b1", "b2", "b3", "a3", "a4", "a5", "b4"], ["c1", "c2", "c3", "c4", "d1", "d2", "d3"], ["e1", "e2", "e3"]]