Posted on 2023-08-18 18:41
Uriel 閱讀(37)
評論(0) 編輯 收藏 引用 所屬分類:
閑來無事重切Leet Code
給出一個無向圖的所有邊，求rank最大的一對節點的rank，rank的定義：
The network rank of two different cities is defined as the total number of directly connected roads to either city. If a road is directly connected to both cities, it is only counted once.
O(n^3)暴力湊合能過
1 #1615
2 #Runtime: 2345 ms (Beats 5.97%)
3 #Memory: 14.6 MB (Beats 97.1%)
4
5 class Solution(object):
6 def maximalNetworkRank(self, n, roads):
7 """
8 :type n: int
9 :type roads: List[List[int]]
10 :rtype: int
11 """
12 g = [[False] * n for _ in range(n)]
13 for x, y in roads:
14 g[x][y] = g[y][x] = True
15 ans = 0
16 for i in range(n):
17 for j in range(n):
18 if i == j:
19 continue
20 t = 0
21 for k in range(n):
22 if k != i and k != j:
23 if g[i][k]:
24 t += 1
25 if g[j][k]:
26 t += 1
27 if g[i][j]:
28 t += 1
29 ans = max(t, ans)
30 return ans