Maximal rank

mail@pastecode.io avatar
unknown
python
2 years ago
1.5 kB
2
Indexable
Never
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