Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一个无向图的所有边,求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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理