aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-01-29 19:31:37 -0700
committerJack Sangdahl <[email protected]>2025-01-29 19:31:37 -0700
commit26f1cc564809ae2f039e22303a0191e9bb060576 (patch)
treef36549f515dfd255f6354f4d70ac00b54592112e
parent2de9d2dce0fd4de524961ad5188a95410f4432c2 (diff)
downloadleetcode-26f1cc564809ae2f039e22303a0191e9bb060576.tar.gz
leetcode-26f1cc564809ae2f039e22303a0191e9bb060576.zip
2493. divide nodes into the maximum number of groups
-rw-r--r--divide_nodes_max_groups.cpp75
-rw-r--r--divide_nodes_max_groups.py66
2 files changed, 141 insertions, 0 deletions
diff --git a/divide_nodes_max_groups.cpp b/divide_nodes_max_groups.cpp
new file mode 100644
index 0000000..ea07a34
--- /dev/null
+++ b/divide_nodes_max_groups.cpp
@@ -0,0 +1,75 @@
+// 2493. Divide Nodes Into the Maximum Number of Groups
+#include "leetcode.h"
+
+/*
+ * you are given a positive integer 'n' representing the number of nodes in an
+ * undirected graph. the nodes are labeled from 1 to 'n'. you are also given a
+ * 2d integer array 'edges', where 'edges[i] = [a_i, b_i]' indicates that there
+ * is a bidirectional edge between nodes 'a_i' and 'b_i'. divide the nodes of
+ * the graph into 'm' groups such that each node in the graph belongs to exactly
+ * one group, and for every pair of nodes in the graph that are connected by an
+ * edge '[a_i, b_i]', then '|y - x| = 1'. return the maximum number of groups
+ * into which you can divide the nodes. return -1 if it is impossible.
+ */
+
+class Solution {
+public:
+ int magnificentSets(int n, vector<vector<int>> &edges) {
+ vector<int> vis(n);
+ vector<vector<int>> graph(n), group;
+ for (auto e : edges) {
+ graph[e[0] - 1].push_back(e[1] - 1);
+ graph[e[1] - 1].push_back(e[0] - 1);
+ }
+ for (int i = 0; i < n; ++i)
+ if (!vis[i]) {
+ vis[i] = true;
+ stack<int> stk;
+ stk.push(i);
+ group.push_back({i});
+ while (stk.size()) {
+ auto u = stk.top();
+ stk.pop();
+ for (auto &v : graph[u])
+ if (!vis[v]) {
+ vis[v] = vis[u] + 1;
+ stk.push(v);
+ group.back().push_back(v);
+ } else if ((vis[u] & 1) == (vis[v] & 1))
+ return -1;
+ }
+ }
+ auto bfs = [&](int x) {
+ int res = 0;
+ vector<bool> vis(n);
+ vis[x] = true;
+ queue<int> q;
+ q.push(x);
+ for (; q.size(); ++res)
+ for (int size = q.size(); size; --size) {
+ auto u = q.front();
+ q.pop();
+ for (auto &v : graph[u])
+ if (!vis[v]) {
+ vis[v] = true;
+ q.push(v);
+ }
+ }
+ return res;
+ };
+ int ans = 0;
+ for (auto &g : group) {
+ transform(g.begin(), g.end(), g.begin(), bfs);
+ ans += *max_element(g.begin(), g.end());
+ }
+ return ans;
+ }
+};
+
+int main() {
+ Solution obj;
+ vvd e1 = {{1, 2}, {1, 4}, {1, 5}, {2, 6}, {2, 3}, {4, 6}};
+ vvd e2 = {{1, 2}, {2, 3}, {3, 1}};
+ printf("%d\n", obj.magnificentSets(6, e1)); // expect: 4
+ printf("%d\n", obj.magnificentSets(3, e2)); // expect: -1
+}
diff --git a/divide_nodes_max_groups.py b/divide_nodes_max_groups.py
new file mode 100644
index 0000000..e6cf7bc
--- /dev/null
+++ b/divide_nodes_max_groups.py
@@ -0,0 +1,66 @@
+# 2493. Divide Nodes Into the Maximum Number of Groups
+from collections import deque
+
+"""
+you are given a positive integer 'n' representing the number of nodes in an
+undirected graph. the nodes are labeled from 1 to 'n'. you are also given a
+2d integer array 'edges', where 'edges[i] = [a_i, b_i]' indicates that there
+is a bidirectional edge between nodes 'a_i' and 'b_i'. divide the nodes of
+the graph into 'm' groups such that each node in the graph belongs to exactly
+one group, and for every pair of nodes in the graph that are connected by an
+edge '[a_i, b_i]', then '|y - x| = 1'. return the maximum number of groups
+into which you can divide the nodes. return -1 if it is impossible.
+"""
+
+
+class Solution(object):
+ def magnificentSets(self, n, edges):
+ """
+ :type n: int
+ :type edges: List[List[int]]
+ :rtype: int
+ """
+ graph = [[] for _ in range(n)]
+ for u, v in edges:
+ graph[u - 1].append(v - 1)
+ graph[v - 1].append(u - 1)
+ vis, group = [0] * n, []
+ for i in range(n):
+ if not vis[i]:
+ vis[i] = True
+ stack = [i]
+ group.append([i])
+ while stack:
+ u = stack.pop()
+ for v in graph[u]:
+ if not vis[v]:
+ vis[v] = vis[u] + 1
+ stack.append(v)
+ group[-1].append(v)
+ elif vis[u] & 1 == vis[v] & 1:
+ return -1
+
+ def bfs(x):
+ res, vis, q = 0, {x}, deque([x])
+ while q:
+ res += 1
+ for _ in range(len(q)):
+ u = q.popleft()
+ for v in graph[u]:
+ if v not in vis:
+ vis.add(v)
+ q.append(v)
+ return res
+
+ ans = 0
+ for g in group:
+ ans += max(bfs(x) for x in g)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.magnificentSets(n=6, edges=[[1, 2], [1, 4], [1, 5], [2, 6], [2, 3], [4, 6]])
+ )
+ print(obj.magnificentSets(n=3, edges=[[1, 2], [2, 3], [3, 1]]))