forked from ngiengkianyew/daily-coding-problem
-
Notifications
You must be signed in to change notification settings - Fork 0
/
problem_279.py
56 lines (43 loc) · 1.07 KB
/
problem_279.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
import random
def populate_group(node, adj_list, group):
group.add(node)
adj_nodes = adj_list[node]
if not adj_nodes:
return
for anode in adj_nodes:
if anode not in group:
populate_group(anode, adj_list, group)
def get_groups(nodes, adj_list, groups):
num_nodes = len(nodes)
while num_nodes:
new_group = set()
node = list(nodes)[0]
populate_group(node, adj_list, new_group)
groups.append(new_group)
nodes -= new_group
num_nodes = len(nodes)
return groups
def get_num_groups(nodes, adj_list):
groups = list()
isolated = set()
for node in nodes:
if not adj_list[node]:
isolated.add(node)
for node in isolated:
groups.append({node})
nodes.remove(node)
del adj_list[node]
groups = get_groups(nodes, adj_list, groups)
print(groups)
return len(groups)
# Tests
adj_list = {
0: [1, 2],
1: [0, 5],
2: [0],
3: [6],
4: [],
5: [1],
6: [3]
}
assert get_num_groups(set(range(7)), adj_list) == 3