并查集---服务器广播

news/2024/11/25 3:13:49/

题目描述
服务器连接方式包括直接相连,间接相连。A和B直接连接,B和C直接连接,则A和C间接连接。直接连接和间接连接都可以发送广播。

给出一个 N * N 数组,代表N个服务器

matrix[i][j] == 1,则代表 i 和 j 直接连接;不等于1时,代表 i 和 j 不直接连接。
matrix[i][i] == 1, 即自己和自己直接连接。
matrix[i][j] == matrix[j][i]。
计算初始需要给几台服务器广播,才可以使每个服务器都收到广播。

输入描述
输入为N行,每行有N个数字,为0或1,由空格分隔,构成N*N的数组,N的范围为 1 <= N <= 40

输出描述
输出一个数字,为需要广播的服务器的数量

用例1
输入
1 0 0
0 1 0
0 0 1
输出
3
说明
3台服务器互不连接,所以需要分别广播这3台服务器

用例2
输入
1 1
1 1
输出
1
说明
2台服务器互相连接,所以只需要广播其中一台服务器

python">class Union:def __init__(self,n):# 初始化并查集,创建一个父节点数组 fa# 每个元素的父节点初始化为它本身self.fa = [i for i in range(n)]#记录当前连通组件的数量self.count = ndef find(self,x):if x!=self.fa[x]:self.fa[x]=self.find(self.fa[x])return self.fa[x]return xdef union(self,x,y):x_fa = self.find(x)y_fa = self.find(y)if x_fa!=y_fa:self.fa[y_fa] = x_faself.count-=1
arrays=[]
while True:try:arrays.append(input().split())except:break
n = len(arrays)
ufs = Union(n)
for i in range(n):for j in range(n):if arrays[i][j]=='1':ufs.union(i,j)
print(ufs.count)

http://www.ppmy.cn/news/1549706.html

相关文章

IText创建加盖公章的pdf文件并生成压缩文件

第一、前言 此前已在文章&#xff1a;Java使用IText根据pdf模板创建pdf文件介绍了Itex的基本使用技巧&#xff0c;本篇以一个案例为基础&#xff0c;主要介绍IText根据pdf模板填充生成pdf文件&#xff0c;并生成压缩文件。 第二、案例 以下面pdf模板为例&#xff0c;生成一个p…

如何使用docker、docker挂载数据,以及让docker使用宿主机器的GPU环境 + docker重启小妙招

最近的工作和学习需要我使用docker&#xff0c;浅浅的学了一下&#xff0c;记录在这&#xff1a;下载docker镜像&#xff0c;用docker打包我的项目和环境&#xff0c;让docker使用宿主机器的GPU环境&#xff0c;将数据挂载在docker容器内&#xff0c;保存一个新的镜像等。最后加…

【大模型推理】vLLM 源码学习

强烈推荐 https://zhuanlan.zhihu.com/p/680153425 sequnceGroup 存储了相同的prompt对应的不同的sequence, 所以用字典存储 同一个Sequence可能占据多个逻辑Block&#xff0c; 所以在Sequence 中用列表存储 同一个block 要维护tokens_id 列表, 需要添加操作。 还需要判断blo…

白蚁自动化监测系统的装置和优势

一、背景 在当今社会&#xff0c;随着科技的飞速发展&#xff0c;智能化、自动化技术在各个领域的应用日益广泛&#xff0c;白蚁自动化监测系统作为一种高效、精准的白蚁防控手段&#xff0c;正逐步成为行业内的主流趋势&#xff0c;既是文物古建水利堤坝等预防性保护的要求&a…

哈希表(极速学习版)

哈希表的定义与实现 概述 哈希表是一种高效的数据结构&#xff0c;它提供了快速的数据插入、删除和查找操作。 通过使用哈希函数&#xff0c;哈希表将输入的键映射到一个指定位置&#xff08;索引&#xff09;以快速访问存储在该位置的值。 哈希表通常用于实现字典、集合、…

SpringCloud框架学习(第五部分:SpringCloud Alibaba入门和 nacos)

目录 十二、SpringCloud Alibaba入门简介 1. 基本介绍 2.作用 3.版本选型 十三、 SpringCloud Alibaba Nacos服务注册和配置中心 1.简介 2.各种注册中心比较 3.下载安装 4.Nacos Discovery服务注册中心 &#xff08;1&#xff09; 基于 Nacos 的服务提供者 &#xf…

Django项目 | 实现登录注册验证电子邮箱

在实现登录验证电子邮箱时&#xff0c;需要确保模型中包含电子邮箱字段 自定义用户模型登录验证电子邮箱实现 1. 模型&#xff08;Model&#xff09; 确保自定义用户模型中包含电子邮箱字段。例如&#xff1a; from django.contrib.auth.models import AbstractUser from d…

数字赋能,气象引领 | 气象景观数字化服务平台重塑京城旅游生态

在数字化转型的浪潮中&#xff0c;旅游行业正以前所未有的速度重塑自身&#xff0c;人民群众对于高品质、个性化旅游服务需求的日益增长&#xff0c;迎着新时代的挑战与机遇&#xff0c;为开展北京地区特色气象景观预报&#xff0c;打造“生态气象旅游”新业态&#xff0c;助推…