题目链接:1615. 最大网络秩
方法:暴力求解
解题思路
初始化每个节点邻接点的数量以及用矩阵保存边的信息,暴力枚举节点对,取其中秩的最大值。
代码
class Solution {
public:
int maximalNetworkRank(int n, vector<vector<int>>& roads) {
vector<vector<int>> g(n, vector<int>(n));
vector<int> num(n);
for (auto &e : roads) {
int u = e[0], v = e[1];
g[u][v] = 1, g[v][u] = 1;
num[u] ++, num[v] ++;
}
int ans = 0;
for (int i = 0; i < n; i ++ ) {
for (int j = i + 1; j < n; j ++ ) {
ans = max(ans, num[i] + num[j] - g[i][j]);
}
}
return ans;
}
};
复杂度分析
时间复杂度:\(O(n^2)\);
空间复杂度:\(O(n^2)\)。