Posted on 2023-08-18 18:41
Uriel 阅读(10)
评论(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