-
-
Notifications
You must be signed in to change notification settings - Fork 40
/
Copy path2493-divide-nodes-into-the-maximum-number-of-groups.py
77 lines (63 loc) · 2.39 KB
/
2493-divide-nodes-into-the-maximum-number-of-groups.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
# time complexity: O(n*(n+m))
# space complexity: O(n)
from collections import deque
from typing import List
class Solution:
def magnificentSets(self, n: int, edges: List[List[int]]) -> int:
adjList = [[] for _ in range(n)]
parent = [-1] * n
depth = [0] * n
for edge in edges:
adjList[edge[0] - 1].append(edge[1] - 1)
adjList[edge[1] - 1].append(edge[0] - 1)
self.union(edge[0] - 1, edge[1] - 1, parent, depth)
numOfGroupsForComponent = {}
for node in range(n):
numberOfGroups = self.getNumberOfGroups(adjList, node, n)
if numberOfGroups == -1:
return -1
root_node = self.find(node, parent)
numOfGroupsForComponent[root_node] = max(
numOfGroupsForComponent.get(root_node, 0), numberOfGroups
)
total_number_of_groups = sum(numOfGroupsForComponent.values())
return total_number_of_groups
def getNumberOfGroups(self, adjList, src_node, n):
nodesQueue = deque()
layerSeen = [-1] * n
nodesQueue.append(src_node)
layerSeen[src_node] = 0
deepestLayer = 0
while nodesQueue:
numOfNodesInLayer = len(nodesQueue)
for _ in range(numOfNodesInLayer):
current_node = nodesQueue.popleft()
for neighbor in adjList[current_node]:
if layerSeen[neighbor] == -1:
layerSeen[neighbor] = deepestLayer + 1
nodesQueue.append(neighbor)
else:
if layerSeen[neighbor] == deepestLayer:
return -1
deepestLayer += 1
return deepestLayer
def find(self, node, parent):
while parent[node] != -1:
node = parent[node]
return node
def union(self, node1, node2, parent, depth):
node1 = self.find(node1, parent)
node2 = self.find(node2, parent)
if node1 == node2:
return
if depth[node1] < depth[node2]:
node1, node2 = node2, node1
parent[node2] = node1
if depth[node1] == depth[node2]:
depth[node1] += 1
n = 6
edges = [[1, 2], [1, 4], [1, 5], [2, 6], [2, 3], [4, 6]]
print(Solution().magnificentSets(n, edges))
n = 3
edges = [[1, 2], [2, 3], [3, 1]]
print(Solution().magnificentSets(n, edges))