刷题笔记合集🔗

题目描述

Linux操作系统有多个发行版，这些发行版之间可能存在关联。例如:

• Ubuntu基于Debian开发
• Mint基于Ubuntu开发
• 则Mint与Debian也存在关联

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

给定一个n×n的矩阵isConnected，其中:

• isConnected[i][j] = 1 表示第i个发行版和第j个发行版直接关联
• isConnected[i][j] = 0 表示二者不直接相连

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

输入格式

第一行输入一个整数N，表示发行版的总数量。 接下来N行，每行N个数字，表示各发行版间是否直接相关。

输出格式

输出一个整数，表示最大的发行版集中发行版的数量。

约束说明

• 1 ≤ N ≤ 200
• 矩阵对称，即isConnected[i][j] = isConnected[j][i]
• 对角线上都是1，即isConnected[i][i] = 1

样例输入1

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

样例输出1

3

样例说明1

• Debian(1)和Ubuntu(2)相关
• Mint(3)和Ubuntu(2)相关
• EulerOS(4)和另外三个都不相关
• 存在两个发行版集:
  1. {Debian, Ubuntu, Mint} 数量为3
  2. {EulerOS} 数量为1
• 输出最大的集合大小3

题目解析

本题考察并查集的应用。关键点:

1. 问题建模

   • 每个发行版是一个节点
   • 直接关联关系是边
   • 要找的是最大连通分量的大小

2. 并查集实现

   • 初始化:每个节点的父节点是自己
   • find:查找节点的根节点(路径压缩)
   • union:合并两个集合

3. 求解步骤

   • 遍历矩阵上三角部分
   • 对于isConnected[i][j]=1的情况合并i,j
   • 统计每个连通分量的大小
   • 返回最大值

时间复杂度: O(N²α(N))，其中α是阿克曼函数的反函数

参考代码

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            px, py = py, px
        self.parent[py] = px
        self.size[px] += self.size[py]
        
def solve():
    # 读取输入
    n = int(input())
    matrix = []
    for _ in range(n):
        row = list(map(int, input().split()))
        matrix.append(row)
    
    # 创建并查集
    uf = UnionFind(n)
    
    # 合并相连的节点
    for i in range(n):
        for j in range(i+1, n):
            if matrix[i][j] == 1:
                uf.union(i, j)
    
    # 找出最大连通分量
    return max(uf.size)

if __name__ == "__main__":
    print(solve())

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class UnionFind {
private:
    vector<int> parent;
    v