forked from lupamo3-zz/coding-interview-gym
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Airport_Connections.py
79 lines (63 loc) · 2.89 KB
/
Airport_Connections.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
def airportConnections(airports, routes, startingAirport):
airportGraph = createAirportGraph(airports, routes)
unreachableAirportNodes = getUnreachableAirportNodes(airportGraph, airports, startingAirport)
markUnreachableConnections(airportGraph, unreachableAirportNodes)
return getMinNumberOfNewConnections(airportGraph, unreachableAirportNodes)
def createAirportGraph(airports, routes):
graph = {}
for airport in airports:
graph[airport] = AirportNode(airport)
for route in routes:
airport, connection = route
graph[airport].connections.append(connection)
return graph
def getUnreachableAirportNodes(airportGraph, airports, startingAirport):
visitedAirports = {}
dfsFromStartingAirport(airportGraph, startingAirport, visitedAirports)
unreachableAirportNodes = []
for airport in airports:
if airport in visitedAirports:
continue
airportNode = airportGraph[airport]
airportNode.isRechable = False
unreachableAirportNodes.append(airportNode)
return unreachableAirportNodes
def dfsFromStartingAirport(airportGraph, startingAirport, visitedAirports):
if startingAirport in visitedAirports:
return
visitedAirports[startingAirport] = True
connections = airportGraph[startingAirport].connections
for connection in connections:
dfsFromStartingAirport(airportGraph, connection, visitedAirports)
def markUnreachableConnections(airportGraph, unreachableAirportNodes):
for airportNode in unreachableAirportNodes:
airport = airportNode.airport
unreachableCOnnections = []
dfsAddUnreachableConnections(airportGraph, airport, unreachableCOnnections, {})
airportNode.unreachableConnections = unreachableCOnnections
def dfsAddUnreachableConnections(airportGraph, airport, unreachableCOnnections, visitedAirports):
if airportGraph[airport].isRechable:
return
if airport in visitedAirports:
return
visitedAirports[airport] = True
unreachableCOnnections.append(airport)
connections = airportGraph[airport].connections
for connection in connections:
dfsAddUnreachableConnections(airportGraph, connection, unreachableCOnnections, visitedAirports)
def getMinNumberOfNewConnections(airportGraph, unreachableAirportNodes):
unreachableAirportNodes.sort(key=lambda airport: len(airport.unreachableConnections), reverse=True)
numberOfNewConnections = 0
for airportNode in unreachableAirportNodes:
if airportNode.isRechable:
continue
numberOfNewConnections += 1
for connection in airportNode.unreachableConnections:
airportGraph[connection].isRechable = True
return numberOfNewConnections
class AirportNode:
def __init__(self, airport):
self.airport = airport
self.connections = []
self.isRechable = True
self.unreachableConnections = []