-
Notifications
You must be signed in to change notification settings - Fork 0
/
exercise6.py
105 lines (83 loc) · 2.48 KB
/
exercise6.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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#!/bin/python3
import math
from math import ceil, sqrt
import os
import random
import re
import sys
import math
def connectedSum(n, edges):
# Write your code here
print('n=', n)
print('edges=', edges)
result = 0
# get nodes that are not in the edges list
connected = set()
isolated = set()
node_range = range(1, n + 1)
for i in node_range:
for e in edges:
if str(i) in e:
connected.add(i)
for i in node_range:
for e in edges:
if str(i) not in e:
if i not in connected:
isolated.add(i)
print('connected=', connected)
print('isolated=', isolated)
# get sets of connected nodes
links = {}
visited = {}
nedges = range(int(len(edges)))
for i in nedges:
node1 = str(edges[int(i)]).split(' ')[0]
node2 = str(edges[int(i)]).split(' ')[1]
if not nodeInKeys(node1, visited):
if not nodeInValues(node1, visited):
visited.update({node1:node2})
links.update({node1:1})
elif nodeInKeys(node1, visited):
if not nodeInValues(node1, visited):
nvalue = int(links.get(node1)) + 1
links.update({node1:nvalue})
if nodeInKeys(node2, visited):
nvalue = int(links.get(node2)) + 1
links.update({node2:nvalue})
links.pop(node1)
print('links', links)
result = getResult(isolated, links)
print('result=', result)
return result
def getResult(isolated, linked):
result = 0
riso = range(1, len(isolated)+ 1)
for i in riso:
result += math.ceil(math.sqrt(1))
for key, value in linked.items():
result += ceil(sqrt(int(value) + 1))
return result
def nodeInKeys(node, d):
for key, value in d.items():
if node == key:
return True
else:
return False
def nodeInValues(node, d):
for key, value in d.items():
if node == value:
return True
else:
return False
def getKeyFromValue(val, d):
for key, value in d.items():
if val == value:
return key
if __name__ == '__main__':
n = 8
edges = ['8 1', '5 8', '7 3', '8 6']
connectedSum(n, edges)
print('')
n = 4
edges = ['1 2', '2 4']
connectedSum(n, edges)