class Solution:
def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
g = [[0] * n for _ in range(n)]
cnt = [0] * n
for a, b in roads:
g[a][b] = g[b][a] = 1
cnt[a] += 1
cnt[b] += 1
return max(cnt[a] + cnt[b] - g[a][b] for a in range(n) for b in range(a + 1, n))
class Solution {
public int maximalNetworkRank(int n, int[][] roads) {
int[][] g = new int[n][n];
int[] cnt = new int[n];
for (var r : roads) {
int a = r[0], b = r[1];
g[a][b] = 1;
g[b][a] = 1;
++cnt[a];
++cnt[b];
}
int ans = 0;
for (int a = 0; a < n; ++a) {
for (int b = a + 1; b < n; ++b) {
ans = Math.max(ans, cnt[a] + cnt[b] - g[a][b]);
}
}
return ans;
}
}
func maximalNetworkRank(n int, roads [][]int) (ans int) {
g := make([][]int, n)
cnt := make([]int, n)
for i := range g {
g[i] = make([]int, n)
}
for _, r := range roads {
a, b := r[0], r[1]
g[a][b], g[b][a] = 1, 1
cnt[a]++
cnt[b]++
}
for a := 0; a < n; a++ {
for b := a + 1; b < n; b++ {
ans = max(ans, cnt[a]+cnt[b]-g[a][b])
}
}
return
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
class Solution:
def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
graph = [set() for _ in range(n)]
for x,y in roads:
graph[x].add(y)
graph[y].add(x)
# 建立邻接表
a,b = 0,0
x,y = [],[]
a,b = heapq.nlargest(2,[len(each) for each in graph])
# 邻接表中边数最多和次多（可以相等）
for i,each in enumerate(graph):
if len(each)==a:
x.append(i)
if len(each)==b:
y.append(i)
# 遍历边数最多和次多的顶点
for i in x:
for j in y:
if i!=j and i not in graph[j]:
return a+b
# 枚举 注意不能是同一个顶点 如果有没有公共边顶点对就返回答案
return a+b-1
class Solution:
def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
adjs = defaultdict(set)
for u,v in roads:
adjs[u].add(v)
adjs[v].add(u)
max_rank = 0
for i in range(n):
for j in range(i+1,n):
rank=len(adjs[i])+len(adjs[j])
if j in adjs[i]:
rank-=1
max_rank=max(max_rank, rank)
return max_rank
