刷题笔记合集🔗

Linux发行版的数量

问题描述

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

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

给你一个 的矩阵 ，其中 表示第 个发行版和第 个发行版直接关联，而 表示二者不直接相连。

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

输入格式

第一行输入发行版的总数量 。

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

输出格式

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

样例输入

4
1 1 0 0
1 1 1 0
0 1 1 0
0 0 0 1

样例输出

3

数据范围

题解

这道题目本质上是求解图中最大连通分量的大小。我们可以将每个Linux发行版看作图中的一个节点，如果两个发行版之间有关联，则在它们之间连一条边。这样，所有互相关联的发行版就构成了一个连通分量，我们需要找出所有连通分量中节点数最多的那个。

求解图的连通分量是一个经典问题，可以使用深度优先搜索(DFS)、广度优先搜索(BFS)或并查集(Union-Find)来解决。在这里，我选择使用并查集，因为它的实现简单且效率高。

并查集是一种树形数据结构，用于管理元素所属的集合，它支持两种主要操作：

1. 查找(Find)：确定元素属于哪个集合
2. 合并(Union)：将两个集合合并成一个

解题步骤：

1. 创建一个并查集，初始时每个发行版自成一个集合
2. 遍历矩阵，对于每个isConnected[i][j] = 1的情况，合并发行版i和j所在的集合
3. 统计每个集合中发行版的数量
4. 返回最大的集合的大小

时间复杂度分析：

• 构建并查集需要O(n)时间
• 遍历矩阵并合并集合需要O(n²)时间，其中每次合并操作的复杂度接近O(1)（使用路径压缩和按秩合并的优化）
• 统计每个集合的大小需要O(n)时间 总体时间复杂度为O(n²)，这对于题目中给出的数据范围(N≤200)是足够高效的。

空间复杂度为O(n)，主要用于存储并查集。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 并查集实现
class UnionFind:
    def __init__(self, n):
        # 初始化，每个节点的父节点是自己
        self.parent = list(range(n))
        # 用于记录每个集合的大小
        self.size = [1] * n
    
    def find(self, x):
        # 路径压缩：查找x的根节点，并将路径上的所有节点直接连到根节点
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # 合并x和y所在的集合
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x != root_y:
            # 将y的根节点连接到x的根节点
            self.parent[root_y] = root_x
            # 更新集合大小
            self.size[root_x] += self.size[root_y]
    
    def get_max_size(self):
        # 获取最大集合的大小
        return max(self.size[self.find(i)] for i in range(len(self.parent)))

# 读取输入
n = int(input())
matrix = []
for _ in range(n):
    matrix.append(list(map(int, input().split())))

# 创建并查集
uf = UnionFind(n)

# 遍历矩阵上三角部分（因为矩阵是对称的）
for i in range(n):
    for j in range(i+1, n):
        if matrix[i][j] == 1:
            uf.union(i, j)

# 输出最大连通分量的大小
print(uf.get_max_size())

• Cpp

#include <bits/stdc++.h>
using namespace std;

// 并查集实现
class UnionFind {
private:
    vector<int> parent; // 记录每个节点的父节点
    vector<int> size;   // 记录每个根节点对应集合的大小
    
public: