Maximal rank
unknown
python
3 years ago
1.5 kB
6
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 graph
Editor is loading...