최대 네트워크 순위

n개의 도시와 이들 도시를 연결하는 roads개의 인프라가 있습니다. 각 roads[i] = [ai, bi]는 도시ai와 bi 사이에 양방향 도로가 있음을 나타냅니다.

서로 다른 두 도시의 네트워크 순위는 각 도시에 직접 연결된 도로의 총 수로 정의됩니다. 도로가 두 도시에 직접 연결된 경우 한 번만 계산됩니다.

인프라의 최대 네트워크 순위는 서로 다른 도시의 모든 쌍의 최대 네트워크 순위입니다.

정수n와 배열roads이 주어지면 전체 인프라의 최대 네트워크 순위를 반환합니다.

예 1:



입력: n = 4, 도로 = [[0,1],[0,3],[1,2],[1,3]]
출력: 4
설명: 도시 0과 1에 연결된 도로가 4개이므로 도시 0과 1의 네트워크 순위는 4입니다. 0과 1 사이의 도로는 한 번만 계산됩니다.

예 2:



입력: n = 5, 도로 = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
출력: 5
설명: 도시 1 또는 2에 연결된 5개의 도로가 있습니다.

예 3:

입력: n = 8, 도로 = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]
출력: 5
설명: 2와 5의 네트워크 순위는 5입니다. 모든 도시가 연결될 필요는 없습니다.

제약:

2 <= n <= 100

0 <= roads.length <= n * (n - 1) / 2

roads[i].length == 2

0 <= ai, bi <= n-1

ai != bi

각 도시 쌍에는 도시를 연결하는 도로가 최대 1개 있습니다.

해결책:

from collections import defaultdict

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        l = len(roads)
        edges = defaultdict(set)
        for k in range(l):
            a, b = roads[k]
            edges[a].add(k)
            edges[b].add(k)
        mnetwork = 0
        for i in range(n):
            for j in range(i + 1, n):
                mnetwork = max(mnetwork, len(set.union(edges[i], edges[j])))
        return mnetwork