【华为OD-E卷 - Linux发行版的数量 100分（python、java、c++、js、c）】

题目

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

用例

用例一：

输入：

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

• 1
• 2
• 3
• 4
• 5

输出：

3

• 1

python解法

• 解题思路：

更新中

• 1

java解法

• 解题思路
• 题目理解：问题是找出一个图中最大的连通分量（也就是一群彼此连接的节点）。在这个问题中，输入的是一个 n x n 的矩阵，表示图的邻接矩阵。矩阵中的每个元素为 1 表示节点之间有边，0 表示没有边。我们要找到这个图中最大的连通分量的大小。

DFS算法：通过深度优先搜索（DFS）遍历图中的每个节点，记录每个连通分量的大小，并更新最大连通分量的大小。

访问标记：为了避免重复遍历，使用一个布尔数组 visited[] 来记录哪些节点已经被访问过。

算法步骤：

对于每个未被访问的节点，调用DFS遍历该节点的连通分量。
对每个连通分量计算大小，并更新最大连通分量的大小。
时间复杂度：DFS遍历所有节点和边，所以时间复杂度是 O(n^2)，适合处理大小为 n 的图。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // 读取矩阵的大小
        int[][] matrix = new int[n][n];  // 创建邻接矩阵

        // 读取邻接矩阵的内容
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = sc.nextInt();  // 填充矩阵
            }
        }

        // 调用函数，计算并输出最大的连通分量大小
        System.out.println(findMaxCluster(matrix, n));
    }

    // 计算最大连通分量的大小
    public static int findMaxCluster(int[][] matrix, int n) {
        boolean[] visited = new boolean[n];  // 记录节点是否被访问过
        int maxSize = 0;  // 最大连通分量的大小

        // 遍历所有节点，找到每个未访问的节点并开始DFS
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {  // 如果节点未被访问过
                int size = dfs(matrix, visited, i, n);  // 深度优先搜索，获取连通分量的大小
                maxSize = Math.max(maxSize, size);  // 更新最大连通分量的大小
            }
        }

        return maxSize;  // 返回最大的连通分量大小
    }

    // 深度优先搜索 (DFS) 计算当前连通分量的大小
    private static int dfs(int[][] matrix, boolean[] visited, int i, int n) {
        visited[i] = true;  // 标记当前节点为已访问
        int size = 1;  // 当前连通分量的大小，初始为1（当前节点）

        // 遍历与当前节点 i 相连的所有节点
        for (int j = 0; j < n; j++) {
            // 如果矩阵[i][j] == 1 且 j 节点没有被访问过，则递归访问 j
            if (matrix[i][j] == 1 && !visited[j]) {
                size += dfs(matrix, visited, j, n);  // 递归DFS，增加连通分量大小
            }
        }

        return size;  // 返回当前连通分量的大小
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52

C++解法

• 解题思路

更新中

• 1

C解法

• 解题思路

更新中

• 1

JS解法

• 解题思路

• 问题理解：

给定一个图的邻接矩阵，我们需要找出图中最大的连通分量的大小。每个节点可以通过边与其他节点相连，连通分量是指一组相互连接的节点。
并查集算法：

使用并查集（Union-Find）算法来解决连通分量的合并与查找问题。并查集是一种高效的数据结构，可以用于解决动态连通性问题。在这个问题中，我们将图中的节点作为并查集的元素，边作为并查集的连接操作。
算法步骤：

初始化并查集：每个节点的父节点初始化为自身。
遍历邻接矩阵：通过双重循环检查所有的边。如果两个节点之间有边，就将它们合并在一起。
统计每个连通分量的大小：通过并查集的 find 操作找到每个节点的根节点，并计算不同根节点的连通分量大小。
返回最大连通分量的大小。
时间复杂度：

由于每个合并和查找操作的时间复杂度是接近常数的（通过路径压缩和按秩合并优化），所以总体时间复杂度为 O(n^2)，其中 n 是节点的数量。

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let graphSize;
const inputLines = [];

// 监听输入
rl.on("line", (line) => {
    inputLines.push(line);  // 将每行输入保存到数组中
    if (inputLines.length === 1) {
        graphSize = Number(inputLines[0]);  // 第一行是图的大小n
    }

    // 读取完图的邻接矩阵数据后处理
    if (graphSize && inputLines.length === graphSize + 1) {
        inputLines.shift(); // 去掉第一行的图大小
        const adjacencyMatrix = parseInput(inputLines);  // 解析邻接矩阵
        const result = findLargestComponent(adjacencyMatrix);  // 查找最大连通分量
        console.log(result);  // 输出结果
        inputLines.length = 0; // 重置输入行数组
    }
});

// 解析输入，生成邻接矩阵
function parseInput(lines) {
    return lines.map((line) => line.split(" ").map(Number));  // 将每行的字符串转换为数字数组
}

// 查找图中最大的连通分量
function findLargestComponent(matrix) {
    const unionFind = new UnionFind(matrix.length);  // 初始化并查集

    // 遍历邻接矩阵中的每一条边
    for (let i = 0; i < matrix.length; i++) {
        for (let j = i + 1; j < matrix.length; j++) {
            if (matrix[i][j] === 1) {  // 如果i和j之间有边
                unionFind.union(i, j);  // 将i和j合并到同一个连通分量中
            }
        }
    }

    // 统计每个连通分量的大小
    const componentSize = {};
    for (let i = 0; i < matrix.length; i++) {
        const root = unionFind.find(unionFind.fa[i]);  // 查找当前节点的根节点
        componentSize[root] = (componentSize[root] || 0) + 1;  // 根据根节点统计连通分量大小
    }

    // 返回最大的连通分量的大小
    return Math.max(...Object.values(componentSize));
}

// 并查集类
class UnionFind {
    constructor(size) {
        this.fa = Array.from({ length: size }, (_, i) => i);  // 初始化父节点数组，每个节点的父节点为其自身
        this.count = size;  // 连通分量的数量
    }

    // 查找操作，带路径压缩优化
    find(x) {
        if (x !== this.fa[x]) {
            this.fa[x] = this.find(this.fa[x]);  // 递归查找根节点，同时压缩路径
        }
        return this.fa[x];  // 返回根节点
    }

    // 合并操作，将x和y所在的连通分量合并
    union(x, y) {
        const rootX = this.find(x);  // 查找x的根节点
        const rootY = this.find(y);  // 查找y的根节点

        if (rootX !== rootY) {
            this.fa[rootY] = rootX;  // 将y的根节点指向x的根节点
            this.count--;  // 连通分量数减少
        }
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏