1
use std::collections::HashMap;
2
use std::collections::HashSet;
3

4
impl Solution {
5
  pub fn restore_array(adjacent_pairs: Vec<Vec<i32>>) -> Vec<i32> {
6
    let mut mp = HashMap::<i32, Vec<i32>>::new();
7

8
    for p in adjacent_pairs {
9
      mp.entry(p[0]).or_insert(vec![]).push(p[1]);
10
      mp.entry(p[1]).or_insert(vec![]).push(p[0]);
11
    }
12

13
    let mut start = 0;
14
    for (k, v) in &mp {
15
      if v.len() == 2 {
16
        continue;
17
      }
18
      start = *k;
19
      break;
20
    }
21

22
    let mut s = HashSet::new();
23
    let mut ret = vec![start];
24
    s.insert(start);
25

26
    while mp.contains_key(&start) {
27
      let mut v = mp.get(&start).unwrap();
28
      let mut done = true;
29
      for u in mp.get(&start).unwrap() {
30
        if s.contains(&u) {
31
          continue;
32
        }
33
        start = *u;
34
        ret.push(*u);
35
        s.insert(*u);
36
        done = false;
37
        break;
38
      }
39
      if done {
40
        break;
41
      }
42
    }
43

44
    ret
45
  }
46
}