网站虚拟主机购买教程,网站建设定义是什么意思,skycc营销软件,微网站自助建站后台文章目录1. 题目2. 解题1. 题目
n 座城市和一些连接这些城市的道路 roads 共同组成一个基础设施网络。 每个 roads[i] [ai, bi] 都表示在城市 ai 和 bi 之间有一条双向道路。
两座不同城市构成的 城市对 的 网络秩 定义为#xff1a;与这两座城市 直接 相连的道路总数。如果…
文章目录1. 题目2. 解题1. 题目
n 座城市和一些连接这些城市的道路 roads 共同组成一个基础设施网络。 每个 roads[i] [ai, bi] 都表示在城市 ai 和 bi 之间有一条双向道路。
两座不同城市构成的 城市对 的 网络秩 定义为与这两座城市 直接 相连的道路总数。如果存在一条道路直接连接这两座城市则这条道路只计算 一次 。
整个基础设施网络的 最大网络秩 是所有不同城市对中的 最大网络秩 。
给你整数 n 和数组 roads返回整个基础设施网络的 最大网络秩 。
示例 1
输入n 4, roads [[0,1],[0,3],[1,2],[1,3]]
输出4
解释城市 0 和 1 的网络秩是 4因为共有 4 条道路与城市 0 或 1 相连。
位于 0 和 1 之间的道路只计算一次。示例 2
输入n 5, roads [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
输出5
解释共有 5 条道路与城市 1 或 2 相连。示例 3
输入n 8, roads [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]
输出5
解释2 和 5 的网络秩为 5注意并非所有的城市都需要连接起来。提示
2 n 100
0 roads.length n * (n - 1) / 2
roads[i].length 2
0 ai, bi n-1
ai ! bi
每对城市之间 最多只有一条 道路相连来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximal-network-rank 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
统计出入度暴力枚举所有情况
class Solution {
public:int maximalNetworkRank(int n, vectorvectorint roads) {vectorint indegree(n, 0);vectorunordered_setint g(n);for(auto r : roads){indegree[r[0]];indegree[r[1]];g[r[0]].insert(r[1]);g[r[1]].insert(r[0]);}int maxRank 0;for(int i 0; i n; i){for(int j 0; j n; j){if(i j) continue;if(g[i].count(j))//有直接相连的边maxRank max(maxRank, indegree[i]indegree[j]-1);elsemaxRank max(maxRank, indegree[i]indegree[j]);}}return maxRank;}
};356 ms 38.3 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
