Leetcode 1615. Maximal Network Rank (python)

题目

暴力解法：

class Solution:def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:graph = collections.defaultdict(int)for road in roads:graph[road[0]] += 1graph[road[1]] += 1ans = 0for i in range(n):for j in range(i+1,n):#print(i,j,temp)tmp = graph[i] + graph[j]if [i,j] in roads or [j,i] in roads:tmp -= 1ans = max(ans,tmp)return ans

邻接矩阵预存边

同时优化了了每个城市边的储存方式，不要太依赖于字典储存

class Solution:def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:degree = [0]*nadj = [[0]*n for _ in range(n)]for road in roads:adj[road[0]][road[1]] = adj[road[1]][road[0]] = 1degree[road[0]] += 1degree[road[1]] += 1ans = 0for 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

c++版本

class Solution {
    
public:int maximalNetworkRank(int n, vector<vector<int>>& roads) {
    vector<int> indegrees(n,0);vector<vector<int>> edges(n,vector<int>(n,0));for(auto& road : roads){
    indegrees[road[0]]++;indegrees[road[1]]++;edges[road[0]][road[1]] = 1;}int ans = 0;for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
    int curr = indegrees[i] + indegrees[j];if(edges[i][j] != 0 || edges[j][i] != 0 ) curr--;ans = max(ans,curr);}}return ans;}
};

时间复杂度：O(n^2)
空间复杂度：O(n^2)
n为节点个数