Maximal rank
unknown
python
4 years ago
1.5 kB
9
Indexable
from collections import deque
class Solution:
def __init__(self):
self.count = 0
self.visited_set = {0}
def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
if len(roads) < 1:
return self.count
distance = 1
graph = self.build_graph(roads)
for i in range(n):
queue = deque([(i, distance)])
while len(queue) > 0:
curr = queue.popleft()
print(curr)
node = curr[0]
for neighbour in graph[node]:
if neighbour not in self.visited_set:
distance += 1
self.visited_set.add(neighbour)
queue.append((neighbour, distance))
return self.count
# def network_rank(self, src, graph, visited, distance):
# if src in visited:
# return 0
# visited.add(src)
# for neighbour in graph[src]:
# distance += 1
# self.network_rank(neighbour, graph, visited, distance)
# return distance
def build_graph(self, edges):
graph = {}
for edge in edges:
a, b = edge[0], edge[1]
if not a in graph:
graph[a] = []
if not b in graph:
graph[b] = []
graph[a].append(b)
graph[b].append(a)
return graphEditor is loading...