leetcode

commit 9098316af92bd6430dc55ee1ab89a5bd47abf1b4
parent 7af105c388d2402e0e59522a6aad325899241266
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 27 Aug 2024 20:44:02 +0200

1 Random Problem

Diffstat:
A
Problems/3249.cpp
 | 
55
+++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 56 insertions(+), 0 deletions(-)
diff --git a/Problems/3249.cpp b/Problems/3249.cpp
@@ -0,0 +1,55 @@
+class Solution {
+  public:
+    int countGoodNodes(const vector<vector<int>> &edges) const {
+        static int count[100001];
+        const int n = size(edges) + 1;
+        vector<vector<int>> adj(n);
+        stack<pair<int, int>> st;
+        int res = 0;
+
+        for (const auto &edge : edges) {
+            adj[edge[0]].push_back(edge[1]);
+            adj[edge[1]].push_back(edge[0]);
+        }
+
+        st.emplace(0, -1);
+        memset(count, 0x00, sizeof(count));
+        while (!st.empty()) {
+            if (st.top().first != -1) {
+                const auto [root, parent] = st.top();
+                st.emplace(-1, -1);
+
+                for (const int next : adj[root]) {
+                    if (next == parent) continue;
+                    st.emplace(next, root);
+                }
+
+                continue;
+            }
+
+            st.pop();
+            const auto [root, parent] = st.top();
+            st.pop();
+
+            int cnt = 1;
+            int goal = -1;
+            bool good = true;
+
+            for (int i = 0; i < size(adj[root]); i++) {
+                const int next = adj[root][i];
+                if (next == parent) continue;
+                if (goal == -1)
+                    goal = count[next];
+                else if (count[next] != goal)
+                    good = false;
+                cnt += count[next];
+            }
+
+            if (good) res++;
+
+            count[root] = cnt;
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -1332,3 +1332,4 @@ for solving problems.
 |  3227  |   Medium   | [Vowels Game in a String](Problems/3227.cpp)                                                       |
 |  3228  |   Medium   | [Maximum Number of Operations to Move Ones to the End](Problems/3228.cpp)                          |
 |  3239  |   Medium   | [Minimum Number of Flips to Make Binary Grid Palindromic I](Problems/3239.cpp)                     |
+|  3249  |   Medium   | [Count the Number of Good Nodes](Problems/3249.cpp)                                                |