Number Of Ways To Reconstruct A Tree LeetCode solution in C++

1
class Solution {
2
 public:
3
  int checkWays(vector<vector<int>> &pairs) {
4
    unordered_map<int, unordered_set<int>> adj;
5
    for (int i = 0; i < pairs.size(); i++) {
6
      adj[pairs[i][0]].emplace(pairs[i][1]);
7
      adj[pairs[i][1]].emplace(pairs[i][0]);
8
    }
9

10
    priority_queue<pair<int, int>> q;
11
    for (auto &[x, arr] : adj) {
12
      q.push({arr.size(), x});
13
    }
14

15
    int n = q.size();
16
    bool multiple = false;
17
    unordered_set<int> seen;
18
    while (!q.empty()) {
19
      auto [sz, v] = q.top();
20
      q.pop();
21

22
      int u = 0;
23
      int usz = n + 1;
24
      if (!seen.empty()) {
25
        for (auto x : adj[v]) {
26
          if (adj[x].size() < usz && seen.count(x)) {
27
            u = x;
28
            usz = adj[x].size();
29
          }
30
        }
31
      }
32

33
      seen.emplace(v);
34
      if (u == 0) {
35
        if (sz != (n - 1)) {
36
          return 0;
37
        }
38
        continue;
39
      }
40

41
      for (auto x : adj[v]) {
42
        if (x == u) {
43
          continue;
44
        }
45

46
        if (!adj[u].count(x)) {
47
          return 0;
48
        }
49
      }
50

51
      if (usz == sz) {
52
        multiple = true;
53
      }
54
    }
55

56
    if (multiple) {
57
      return 2;
58
    }
59

60
    return 1;
61
  }
62
};