HardNo. 2493
Divide Nodes Into the Maximum Number of Groups — LeetCode 2493 Python Solution
- Pattern
- Union-Find
- Topics
- Depth-First Search, Breadth-First Search, Union Find, Graph
- Reading time
- 5 min
- Source
- leetcode.com
The problem
You are given a positive integer n representing the number of nodes in an undirected graph. The nodes are labeled from 1 to n.
Example
- Input
- n = 6, edges = [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]
- Output
- 4
- Explanation
- As shown in the image we:
Python solution
class Solution:
def magnificentSets(self, n: int, edges: List[List[int]]) -> int:
g = [[] for _ in range(n)]
for a, b in edges:
g[a - 1].append(b - 1)
g[b - 1].append(a - 1)
d = defaultdict(int)
for i in range(n):
q = deque([i])
dist = [0] * n
dist[i] = mx = 1
root = i
while q:
a = q.popleft()
root = min(root, a)
for b in g[a]:
if dist[b] == 0:
dist[b] = dist[a] + 1
mx = max(mx, dist[b])
q.append(b)
elif abs(dist[b] - dist[a]) != 1:
return -1
d[root] = max(d[root], mx)
return sum(d.values())Complexity
- Time
- O(n × (n + m))
- Space · auxiliary
- O(n + m)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2493. Divide Nodes Into the Maximum Number of Groups is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2492 | Minimum Score of a Path Between Two Cities | Medium |
| 0399 | Evaluate Division | Medium |
| 0547 | Number of Provinces | Medium |
| 0684 | Redundant Connection | Medium |
| 0685 | Redundant Connection II | Hard |
| 0785 | Is Graph Bipartite? | Medium |
Frequently asked questions
- How hard is LeetCode 2493. Divide Nodes Into the Maximum Number of Groups?
LeetCode 2493. Divide Nodes Into the Maximum Number of Groups is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2493. Divide Nodes Into the Maximum Number of Groups?
The Python solution on this page runs in O(n × (n + m)).
- What is the space complexity of LeetCode 2493. Divide Nodes Into the Maximum Number of Groups?
The Python solution on this page uses O(n + m) auxiliary space.
- What topics does LeetCode 2493. Divide Nodes Into the Maximum Number of Groups cover?
LeetCode 2493. Divide Nodes Into the Maximum Number of Groups is tagged Depth-First Search, Breadth-First Search, Union Find and Graph on LeetCode.