leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

3203.cpp (1244B)

      1 class Solution {
      2     using vvi = vector<vector<int>>;
      3 
      4     static int middle(const vvi &edges) {
      5         static int count[100001];
      6         const int n = size(edges) + 1;
      7         vvi adj(n);
      8 
      9         memset(count, 0x00, sizeof(count));
     10 
     11         for (const auto &edge : edges) {
     12             adj[edge[0]].push_back(edge[1]);
     13             adj[edge[1]].push_back(edge[0]);
     14             count[edge[0]]++;
     15             count[edge[1]]++;
     16         }
     17 
     18         queue<int> q;
     19         for (int i = 0; i < n; i++) {
     20             if (count[i] != 1) continue;
     21             q.push(i);
     22         }
     23 
     24         int crnt = 0, left = n, lvl;
     25         for (lvl = 0; left > 2; lvl++) {
     26             left -= size(q);
     27 
     28             for (int k = size(q); k > 0; k--) {
     29                 crnt = q.front(), q.pop();
     30 
     31                 for (const auto next : adj[crnt]) {
     32                     if (--count[next] != 1) continue;
     33                     q.push(next);
     34                 }
     35             }
     36         }
     37 
     38         return 2 * lvl + (left == 2);
     39     }
     40 
     41   public:
     42     int minimumDiameterAfterMerge(const vvi &edges1, const vvi &edges2) const {
     43         const auto d1 = middle(edges1);
     44         const auto d2 = middle(edges2);
     45 
     46         return max({d1, d2, (d1 + 1) / 2 + (d2 + 1) / 2 + 1});
     47     }
     48 };