Linux发行版的数量

华为OD机试

题目描述

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

题解

问题分析

我们需要找出一个最大“发行版集”的大小，定义为在给定的矩阵 isConnected 中，元素为 1 的地方表示两个操作系统之间直接关联，而 0 表示不直接关联。我们需要将所有直接或间接关联的操作系统归为一组，最终返回最大的关联组（即连通分量）的大小。

解决这个问题时，利用 并查集（Union-Find）来处理集合的合并与查询是非常高效的。这里我们不使用秩（rank）优化，仅使用基本的路径压缩和合并操作。

并查集算法步骤

初始化：每个操作系统自成一个集合。

Union：当 isConnected[i][j] = 1 时，将操作系统 i 和 j 合并为一个集合。

Find：查找一个操作系统所在的集合的根节点。

计算：每次合并后，统计每个集合的大小，最终返回最大的集合大小。

C++

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

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

public:
    UnionFind(int n) {
        parent.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // 每个元素的父节点是自己
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩
        }
        return parent[x];
    }

    void unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;  // 合并
            size[rootY] += size[rootX];  // 更新集合大小
        }
    }

    int getSize(int x) {
        return size[find(x)];
    }
};

int main() {
    int n;
    cin >> n;
    vector<vector<int>> isConnected(n, vector<int>(n));

    // 输入
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> isConnected[i][j];
        }
    }

    // 并查集初始化
    UnionFind uf(n);

    // 合并操作
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (isConnected[i][j] == 1) {
                uf.unionSet(i, j);
            }
        }
    }

    // 查找最大的集
    int max = 0;
    for (int i = 0; i < n; i++) {
        max = std::max(max, uf.getSize(i));
    }

    cout << max << endl;  // 输出结果
    return 0;
}