隆昌住房和城乡建设官方网站,看网站的浏览器,义乌北苑编程网站开发公司,国家企业信息服务平台文章目录 前言一、题目二、代码分析总结 前言
这题挺有意思#xff0c;感觉评简单难度有点低了#xff0c;如果正经用无向图来做#xff0c;代码还是有点长的。首先得建立节点#xff0c;估计除第一个和最后一个每个节点都是一条线连进#xff0c;一条线连出的。就可以这… 文章目录 前言一、题目二、代码分析总结 前言
这题挺有意思感觉评简单难度有点低了如果正经用无向图来做代码还是有点长的。首先得建立节点估计除第一个和最后一个每个节点都是一条线连进一条线连出的。就可以这样设计节点然后生成树最后深度搜索。既然都是简单评价了咱就用个简单的解法。这题和有一道参加宴会介绍人认识的题目很像都可以用集合来解而且更容易让人理解。 提示以下是本篇文章正文内容下面案例可供参考
一、题目
题目描述 小蚂蚁群是一个庞大的群体在这个蚂蚁群中有n只小蚂蚁 为了保证所有蚂蚁在消息传送的时候都能接收到消息需要在他们之间建立通信关系。就是要求小蚂蚁都可以通过多只或者直接联系到其他人。 已知几条小蚂蚁之间有通信关系请问还需要再新建至少多少条关系
输入描述 第一行输入整数nmn为小蚂蚁总数m为关系数。(1n,m1000) 以下m行每行m对整数xy。(代表x与y有联系)
输出描述 输出最少需要新建关系数。
二、代码分析
代码如下示例 def solution(self, n, m, vector):result None# TODO: 请在此编写代码if vector.__len__() 0:return n-1relation [set(vector[0])] # 用于存放有联系的集合rl 1 # 上面集合的长度手动写会快些本身也是可知的for x in vector: # 查找联系生成集合setx set(x)for j in range(rl):if ( not relation[j].isdisjoint(setx) ):relation[j] relation[j].union(setx)breakelif j rl-1:relation.append(setx)rl 1part relation.__len__()- # 团体间无联系的数量-1是需要几个新建的联系rela_all set() # 所有已参加团体的蚂蚁for x in relation:rela_all rela_all.union(x)rela_all len(rela_all)result part n - rela_all return result看注释也就明白了很简单的逻辑 1、如果关系列表是空的则需要新建n-1个关系。嗯偷偷告诉你们有这样的数据6900[ ]。
2、默认第一个关系为一个小团体的初始设置rl 1因为所有新增小团体都是下面代码生成的是可知的所以此处写死了团体数量。下面的循环有相应的代码来增加这个值很明显题目是要求无向图的咱写集合肯定得考虑效率问题。事实上不用集合直接用列表查询会超时别问我咋知道的…
3、稍微有点复杂的就是关系集合生成这一步了代码中x是每对关系先变成集合。然后去列表中的小团体集合查询有就加入没有就新建一个小团体。其中 isdisjoint 是判断是否交集这是个否定判断。意思是“是不是不是交集” 呃~ 这要晕的换个说法 “是否非交集”。返回 True 表示的是不是交集。所以笔者在这里加了not当是交集的时候就加入。下面的else要判断是不是最后一个小团体。因为 ralation 列表中可能有很多小团体集合所以每次要遍历。只有当是最后一个小团体了上面的代码又没将 x 加入才新建一个小团体同时将列表长度 rl 加1。
4、如上我们就得到了所有的小团体这里用 part 变量表示。显然小团体之间需要一个联系就够了所以这里是小团体数减1。
5、再然后我们需要知道所有已加入小团体的蚂蚁数。这里用了一个 for 循环。全加入到一个集合中union 是并集运算。
6、最后小团体之间需要的联系数加上蚂蚁数减去已参加小团体的数就是答案了。 总结
本想再用无向图搜索解一遍的偷懒了~
