Leetcode 1615. Maximal Network Rank
题目暴力解法：邻接矩阵预存边
题目
暴力解法：
class Solution:
def maximalNetworkRank(self
, n
: int, roads
: List
[List
[int]]) -> int:
graph
= collections
.defaultdict
(int)
for road
in roads
:
graph
[road
[0]] += 1
graph
[road
[1]] += 1
ans
= 0
for i
in range(n
):
for j
in range(i
+1,n
):
tmp
= graph
[i
] + graph
[j
]
if [i
,j
] in roads
or [j
,i
] in roads
:
tmp
-= 1
ans
= max(ans
,tmp
)
return ans
邻接矩阵预存边
同时优化了了每个城市边的储存方式，不要太依赖于字典储存
class Solution:
def maximalNetworkRank(self
, n
: int, roads
: List
[List
[int]]) -> int:
degree
= [0]*n
adj
= [[0]*n
for _
in range(n
)]
for road
in roads
:
adj
[road
[0]][road
[1]] = adj
[road
[1]][road
[0]] = 1
degree
[road
[0]] += 1
degree
[road
[1]] += 1
ans
= 0
for i
in range(n
):
for j
in range(i
+1,n
):
tmp
= degree
[i
] + degree
[j
] - adj
[i
][j
]
ans
= max(ans
,tmp
)
return ans
