首页 > 系统相关 >并查集---Linux发行版的数量

并查集---Linux发行版的数量

时间:2024-11-01 19:52:01浏览次数:5  
标签:__ self 查集 find --- fa 发行版 Linux 节点

题目描述
Linux操作系统有多个发行版,distrowatch.com提供了各个发行版的资料。这些发行版互相存在关联,例如Ubuntu基于Debian开发,而Mint又基于Ubuntu开发,那么我们认为Mint同Debian也存在关联。

发行版集是一个或多个相关存在关联的操作系统发行版,集合内不包含没有关联的发行版。

给你一个 n * n 的矩阵 isConnected,其中 isConnected[i][j] = 1 表示第 i 个发行版和第 j 个发行版直接关联,而 isConnected[i][j] = 0 表示二者不直接相连。

返回最大的发行版集中发行版的数量。

输入描述
第一行输入发行版的总数量N,

之后每行表示各发行版间是否直接相关

输出描述
输出最大的发行版集中发行版的数量

备注
1 ≤ N ≤ 200

用例1
输入
4
1 1 0 0
1 1 1 0
0 1 1 0
0 0 0 1
输出
3
说明
Debian(1)和Unbuntu2)相关

Mint(3)和Ubuntu(2)相关,

EeulerOS(4)和另外三个都不相关,

所以存在两个发行版集,发行版集中发行版的数量分别是3和1,所以输出3。

class UnionFindSet:
    def __init__(self, n):
        # 初始化并查集,每个结点自成一个集合,代表自身
        self.fa = [idx for idx in range(n)]  # 初始化父节点,每个节点的父节点最初设为自身

    def find(self, x):
        # 查找操作,递归寻找x的根节点,并压缩路径
        if x != self.fa[x]:
            self.fa[x] = self.find(self.fa[x])  # 压缩路径,直接指向根节点
            return self.fa[x]  # 返回根节点
        return x  # 返回自身,代表根节点

    def union(self, x, y):
        # 合并操作,将x的根节点指向y的根节点
        # 找到x和y的根节点
        x_fa = self.find(x)
        y_fa = self.find(y)
        if x_fa != y_fa:
            self.fa[y_fa] = x_fa  # 将y的根节点指向x的根节点

if __name__ == '__main__':
    n = int(input())  # 输入结点数量n
    matrix = []
    # 输入n行n列的矩阵,表示结点之间的连接关系
    for i in range(n):
        matrix.append(list(map(int, input().split())))

    ufs = UnionFindSet(n)  # 创建并查集对象

    # 遍历矩阵,如果两个结点有连接关系,则合并它们
    for i in range(n):
        for j in range(i + 1, n):
            if matrix[i][j] == 1:
                ufs.union(i, j)  # 将有连接关系的结点进行合并

    connected = {}  # 记录每个集合的大小
    for i in range(n):
        fa = ufs.find(ufs.fa[i])  # 找到i所在集合的根节点
        connected[fa] = connected.get(fa, 0) + 1  # 计算集合的大小

    # 输出最大集合的大小
    print(max(connected.values()))

标签:__,self,查集,find,---,fa,发行版,Linux,节点
From: https://blog.csdn.net/TTz012/article/details/143439658

相关文章

  • 牛客软件开发专项练习-Day2
    1.下列叙述中正确的是(A)A.顺序存储结构的存储一定是连续的,链式存储结构的存储空间不一定是连续的B.顺序存储结构只针对线性结构,链式存储结构只针对非线性结构C.顺序存储结构能存储有序表,链式存储结构不能存储有序表D.链式存储结构比顺序存储结构节省存储空间解释:链式存储结......
  • [NPUCTF2020]Anti-IDA
    [NPUCTF2020]Anti-IDAbuuctf刷题碰到的。没见到网上有wp就写一份吧很多无关的操作,只要不对输入数据影响就不需要管,最后exp如下enc=b"\x33\x44\x33\x39\x33\x41\x33\x37\x33\x34\x33\x43\x33\x39\x33\x37\x33\x41\x33\x34\x33\x41\x33\x37\x33\x44\x33\x36\x33\x36\x33\x41\......
  • 牛客软件开发专项练习-Day4
    1.下面关于并行和并发的区别,说法错误的是(C)A.并发计算是一种程序计算的形式,在系统中,至少有两个以上的计算在同时运作,计算结果可能同时发生B.并行计算指许多指令得以同时进行的计算模式。在同时进行的前提下,可以将计算的过程分解成小部份,之后以并发方式来加以解决C.并行是同时......
  • 2024 -- 国庆集训 -- 临沂四中 -- 10月01 日 -- S/N模拟赛#1 题解
    A.2025--[炼石计划--NOIP模拟三]--T1--矩形赛时草了个\(O(n^4\log(n))\)竟然能过70分虽然本来就是这么分配的,发现正解只需将二分改为双指针就可以了,最气的是上面计算的时候用到还是尺取下面就用的二分(唐诗)。其实这题就是暴力,然后在低级的暴力上加一些操作变得稍微高级一......
  • CSP-S2024复盘
    CSP-S2024复盘好的:没有陷入100+100+100+0陷阱不好:写得太慢了痛失AK机会T1想得太慢了,没有观察样例读题的习惯所导致的,之后读题的时候应该大概理解完题意之后去看样例解释确保读对题以后再开始想。T2写的太慢了,第一次使用键盘在桌子下的电脑导致适应了15min才调整到了能......
  • [CSP-S 2024] 超速检测
    前言寄!算法计算超速区间容易发现可以计算出每一辆车的超速区间分讨策略大致如下voidCalc(intNow){if(Car[Now].v>V){if(Car[Now].a>=0){Car[Now].Left=Car[Now].d,Car[Now].Right=L;return;......
  • 《Linux系统编程篇》fork/wait/waitpid/exit函数——基础篇
    文章目录引言fork()函数概述父子进程兄弟进程fork函数fork()的常见问题fork()的优势与限制引入`wait`和`waitpid`(解决僵尸进程)wait函数waitpid函数:exit函数结论命为志存。——朱熹引言《Linux系统编程篇》——基础篇首页传送门本节我们正式进入Linux的进......
  • 《Linux系统编程篇》消息队列(Linux 进程间通信(IPC))——基础篇
    文章目录引言消息队列(MessageQueue)消息队列的特点消息队列的特性消息队列的操作ipcs-q拓展ipcrm拓展注意事项结论“山重水复疑无路,柳暗花明又一村。”——陆游引言《Linux系统编程篇》——基础篇首页传送门想象一下,你正在开发一个多任务处理的应用程序,其中......
  • 计蒜客:修建大桥(并查集/DFS/BFS)
     找到有几张连通图即可解决问题。DFS:1#include<bits/stdc++.h>2usingnamespacestd;3intn,m;4intgraph[1005][1005]={0};5boolvisited[1005]={false};6voiddfs(intp){7if(visited[p]){8return;9}10visited[p]......
  • 2024-11-1-leetcode每日一题-3259. 超级饮料的最大强化能量
    题目描述来自未来的体育科学家给你两个整数数组 energyDrinkA 和 energyDrinkB,数组长度都等于 n。这两个数组分别代表A、B两种不同能量饮料每小时所能提供的强化能量。你需要每小时饮用一种能量饮料来 最大化 你的总强化能量。然而,如果从一种能量饮料切换到另一种,你......