leetcode

0 class Solution {

1 using vvi = vector<vector<int>>;

2

3 static int middle(const vvi &edges) {

4 static int count[100001];

5 const int n = size(edges) + 1;

6 vvi adj(n);

7

8 memset(count, 0x00, sizeof(count));

9

10 for (const auto &edge : edges) {

11 adj[edge[0]].push_back(edge[1]);

12 adj[edge[1]].push_back(edge[0]);

13 count[edge[0]]++;

14 count[edge[1]]++;

15 }

16

17 queue<int> q;

18 for (int i = 0; i < n; i++) {

19 if (count[i] != 1) continue;

20 q.push(i);

21 }

22

23 int crnt = 0, left = n, lvl;

24 for (lvl = 0; left > 2; lvl++) {

25 left -= size(q);

26

27 for (int k = size(q); k > 0; k--) {

28 crnt = q.front(), q.pop();

29

30 for (const auto next : adj[crnt]) {

31 if (--count[next] != 1) continue;

32 q.push(next);

33 }

34 }

35 }

36

37 return 2 * lvl + (left == 2);

38 }

39

40 public:

41 int minimumDiameterAfterMerge(const vvi &edges1, const vvi &edges2) const {

42 const auto d1 = middle(edges1);

43 const auto d2 = middle(edges2);

44

45 return max({d1, d2, (d1 + 1) / 2 + (d2 + 1) / 2 + 1});

46 }

47 };