leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1443.cpp (1079B)

0 class Solution { 1 public: 2 int minTime(int n, vector<vector<int>> &edges, vector<bool> &hasApple) { 3 vector<vector<int>> adj(n, vector<int>()); 4 for (auto &e : edges) { 5 adj[e[0]].push_back(e[1]); 6 adj[e[1]].push_back(e[0]); 7 } 8 9 stack<pair<int, int>> st; 10 int res = 0; 11 12 st.push({0, -1}); 13 while (!st.empty()) { 14 if (st.top().first == -1) { 15 st.pop(); 16 17 auto [crnt, par] = st.top(); 18 st.pop(); 19 int count = 0; 20 21 for (int c : adj[crnt]) { 22 if (c == par) continue; 23 count += hasApple[c]; 24 } 25 26 res += count; 27 hasApple[crnt] = hasApple[crnt] || count; 28 continue; 29 } 30 31 auto [crnt, par] = st.top(); 32 st.push({-1, -1}); 33 34 for (int c : adj[crnt]) { 35 if (c == par) continue; 36 st.push({c, crnt}); 37 } 38 } 39 40 return res * 2; 41 } 42 };