diff options
author | Jack Sangdahl <[email protected]> | 2025-01-29 19:31:37 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-29 19:31:37 -0700 |
commit | 26f1cc564809ae2f039e22303a0191e9bb060576 (patch) | |
tree | f36549f515dfd255f6354f4d70ac00b54592112e | |
parent | 2de9d2dce0fd4de524961ad5188a95410f4432c2 (diff) | |
download | leetcode-26f1cc564809ae2f039e22303a0191e9bb060576.tar.gz leetcode-26f1cc564809ae2f039e22303a0191e9bb060576.zip |
2493. divide nodes into the maximum number of groups
-rw-r--r-- | divide_nodes_max_groups.cpp | 75 | ||||
-rw-r--r-- | divide_nodes_max_groups.py | 66 |
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]])) |