【华为OD】Linux发行版的数量

发布于：2025-09-11 ⋅ 阅读:(14) ⋅ 点赞:(0)

【华为OD】Linux发行版的数量

题目描述

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

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

给你一个 n x 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

输出：

3

说明：
Debian(1)和 Ubuntu(2)相关，Mint(3)和 Ubuntu(2)相关，EeulerOS(4)和另外三个都不相关，所以存在两个发行版集，发行版集中发行版的数量分别是 3 和 1，所以输出 3

解题思路

这是一个典型的无向图连通分量问题。我们需要找到图中最大连通分量的大小。

核心思想：

  1. 将发行版关联矩阵看作无向图的邻接矩阵
  2. 使用图遍历算法（DFS或BFS）找出所有连通分量
  3. 返回最大连通分量的节点数量

关键概念：

  • 连通分量：图中任意两个节点都可以通过路径相互到达的最大子图
  • 邻接矩阵：isConnected[i][j] = 1 表示节点i和节点j直接相连

我将提供两种解法：深度优先搜索法（DFS）和广度优先搜索法（BFS）。

解法一：深度优先搜索法（DFS）

使用DFS遍历图，对每个未访问的节点开始DFS，统计每个连通分量的大小。

Java实现

import java.util.*;

public class Solution1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[][] isConnected = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                isConnected[i][j] = sc.nextInt();
            }
        }
        
        int result = findLargestComponent(isConnected, n);
        System.out.println(result);
        
        sc.close();
    }
    
    private static int findLargestComponent(int[][] isConnected, int n) {
        boolean[] visited = new boolean[n];
        int maxSize = 0;
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                int size = dfs(isConnected, visited, i, n);
                maxSize = Math.max(maxSize, size);
            }
        }
        
        return maxSize;
    }
    
    private static int dfs(int[][] isConnected, boolean[] visited, int node, int n) {
        visited[node] = true;
        int size = 1; // 当前节点计入大小
        
        for (int i = 0; i < n; i++) {
            if (isConnected[node][i] == 1 && !visited[i]) {
                size += dfs(isConnected, visited, i, n);
            }
        }
        
        return size;
    }
}

Python实现

def dfs(is_connected, visited, node, n):
    visited[node] = True
    size = 1  # 当前节点计入大小
    
    for i in range(n):
        if is_connected[node][i] == 1 and not visited[i]:
            size += dfs(is_connected, visited, i, n)
    
    return size

def find_largest_component(is_connected, n):
    visited = [False] * n
    max_size = 0
    
    for i in range(n):
        if not visited[i]:
            size = dfs(is_connected, visited, i, n)
            max_size = max(max_size, size)
    
    return max_size

def solve_dfs():
    n = int(input())
    is_connected = []
    
    for _ in range(n):
        row = list(map(int, input().split()))
        is_connected.append(row)
    
    result = find_largest_component(is_connected, n)
    print(result)

solve_dfs()

C++实现

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

int dfs(vector<vector<int>>& isConnected, vector<bool>& visited, int node, int n) {
    visited[node] = true;
    int size = 1; // 当前节点计入大小
    
    for (int i = 0; i < n; i++) {
        if (isConnected[node][i] == 1 && !visited[i]) {
            size += dfs(isConnected, visited, i, n);
        }
    }
    
    return size;
}

int findLargestComponent(vector<vector<int>>& isConnected, int n) {
    vector<bool> visited(n, false);
    int maxSize = 0;
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            int size = dfs(isConnected, visited, i, n);
            maxSize = max(maxSize, size);
        }
    }
    
    return maxSize;
}

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];
        }
    }
    
    int result = findLargestComponent(isConnected, n);
    cout << result << endl;
    
    return 0;
}

解法二：广度优先搜索法（BFS）

使用BFS遍历图，对每个未访问的节点开始BFS，统计每个连通分量的大小。

Java实现

import java.util.*;

public class Solution2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[][] isConnected = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                isConnected[i][j] = sc.nextInt();
            }
        }
        
        int result = findLargestComponentBFS(isConnected, n);
        System.out.println(result);
        
        sc.close();
    }
    
    private static int findLargestComponentBFS(int[][] isConnected, int n) {
        boolean[] visited = new boolean[n];
        int maxSize = 0;
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                int size = bfs(isConnected, visited, i, n);
                maxSize = Math.max(maxSize, size);
            }
        }
        
        return maxSize;
    }
    
    private static int bfs(int[][] isConnected, boolean[] visited, int start, int n) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;
        int size = 0;
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            size++;
            
            for (int i = 0; i < n; i++) {
                if (isConnected[node][i] == 1 && !visited[i]) {
                    visited[i] = true;
                    queue.offer(i);
                }
            }
        }
        
        return size;
    }
}

Python实现

from collections import deque

def bfs(is_connected, visited, start, n):
    queue = deque([start])
    visited[start] = True
    size = 0
    
    while queue:
        node = queue.popleft()
        size += 1
        
        for i in range(n):
            if is_connected[node][i] == 1 and not visited[i]:
                visited[i] = True
                queue.append(i)
    
    return size

def find_largest_component_bfs(is_connected, n):
    visited = [False] * n
    max_size = 0
    
    for i in range(n):
        if not visited[i]:
            size = bfs(is_connected, visited, i, n)
            max_size = max(max_size, size)
    
    return max_size

def solve_bfs():
    n = int(input())
    is_connected = []
    
    for _ in range(n):
        row = list(map(int, input().split()))
        is_connected.append(row)
    
    result = find_largest_component_bfs(is_connected, n)
    print(result)

solve_bfs()

C++实现

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

int bfs(vector<vector<int>>& isConnected, vector<bool>& visited, int start, int n) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    int size = 0;
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        size++;
        
        for (int i = 0; i < n; i++) {
            if (isConnected[node][i] == 1 && !visited[i]) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
    
    return size;
}

int findLargestComponentBFS(vector<vector<int>>& isConnected, int n) {
    vector<bool> visited(n, false);
    int maxSize = 0;
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            int size = bfs(isConnected, visited, i, n);
            maxSize = max(maxSize, size);
        }
    }
    
    return maxSize;
}

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];
        }
    }
    
    int result = findLargestComponentBFS(isConnected, n);
    cout << result << endl;
    
    return 0;
}

解法三：并查集法（Union-Find）

使用并查集数据结构来解决连通分量问题，这是另一种经典方法。

Java实现

import java.util.*;

public class Solution3 {
    static class UnionFind {
        private int[] parent;
        private int[] size;
        private int maxSize;
        
        public UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            maxSize = 1;
            
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }
        
        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]); // 路径压缩
            }
            return parent[x];
        }
        
        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            
            if (rootX != rootY) {
                // 按大小合并
                if (size[rootX] < size[rootY]) {
                    int temp = rootX;
                    rootX = rootY;
                    rootY = temp;
                }
                
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
                maxSize = Math.max(maxSize, size[rootX]);
            }
        }
        
        public int getMaxSize() {
            return maxSize;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        UnionFind uf = new UnionFind(n);
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int connected = sc.nextInt();
                if (connected == 1 && i != j) {
                    uf.union(i, j);
                }
            }
        }
        
        System.out.println(uf.getMaxSize());
        sc.close();
    }
}

Python实现

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.max_size = 1
    
    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):
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x != root_y:
            # 按大小合并
            if self.size[root_x] < self.size[root_y]:
                root_x, root_y = root_y, root_x
            
            self.parent[root_y] = root_x
            self.size[root_x] += self.size[root_y]
            self.max_size = max(self.max_size, self.size[root_x])
    
    def get_max_size(self):
        return self.max_size

def solve_union_find():
    n = int(input())
    uf = UnionFind(n)
    
    for i in range(n):
        row = list(map(int, input().split()))
        for j in range(n):
            if row[j] == 1 and i != j:
                uf.union(i, j)
    
    print(uf.get_max_size())

solve_union_find()

C++实现

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

class UnionFind {
private:
    vector<int> parent;
    vector<int> size;
    int maxSize;
    
public:
    UnionFind(int n) : parent(n), size(n, 1), maxSize(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 unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY) {
            // 按大小合并
            if (size[rootX] < size[rootY]) {
                swap(rootX, rootY);
            }
            
            parent[rootY] = rootX;
            size[rootX] += size[rootY];
            maxSize = max(maxSize, size[rootX]);
        }
    }
    
    int getMaxSize() {
        return maxSize;
    }
};

int main() {
    int n;
    cin >> n;
    
    UnionFind uf(n);
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int connected;
            cin >> connected;
            if (connected == 1 && i != j) {
                uf.unite(i, j);
            }
        }
    }
    
    cout << uf.getMaxSize() << endl;
    return 0;
}

算法复杂度分析

解法一：深度优先搜索法（DFS）

  • 时间复杂度：O(N²)，需要遍历整个邻接矩阵
  • 空间复杂度：O(N)，递归栈深度和visited数组

解法二：广度优先搜索法（BFS）

  • 时间复杂度：O(N²)，需要遍历整个邻接矩阵
  • 空间复杂度：O(N)，队列和visited数组

解法三：并查集法（Union-Find）

  • 时间复杂度：O(N² × α(N))，其中α是阿克曼函数的反函数，实际上近似O(N²)
  • 空间复杂度：O(N)，parent和size数组

算法原理详解

核心思想

这个问题本质上是求无向图的最大连通分量大小。三种解法的核心思想：

  1. DFS/BFS：通过图遍历找到所有连通分量
  2. 并查集：通过合并操作将相连的节点归并到同一集合

关键概念

  1. 连通分量：图中任意两个节点都可以通过路径相互到达的最大子图
  2. 邻接矩阵：isConnected[i][j] = 1 表示节点i和节点j直接相连
  3. 传递性：如果A连B，B连C，则A和C在同一连通分量中

三种解法的特点

  1. DFS法：

    • 递归实现，代码简洁
    • 适合理解连通性概念
    • 可能存在栈溢出风险（深度过大）

  2. BFS法：

    • 迭代实现，使用队列
    • 层次遍历，逻辑清晰
    • 空间使用相对稳定

  3. 并查集法：

    • 专门解决动态连通性问题
    • 支持高效的合并和查找操作
    • 代码相对复杂，但概念重要

示例分析

示例详细分析

给定邻接矩阵：

1 1 0 0
1 1 1 0
0 1 1 0
0 0 0 1

连通关系分析：

  • 节点0和节点1直接相连
  • 节点1和节点2直接相连
  • 通过传递性：节点0、1、2构成一个连通分量
  • 节点3独立，构成另一个连通分量

连通分量：

  1. {0, 1, 2}，大小为3
  2. {3}，大小为1

最大连通分量大小为3，所以答案是3。

图示表示

发行版关系图：
Debian(0) ——— Ubuntu(1) ——— Mint(2)
                              
EeulerOS(3) (独立)

连通分量1: {Debian, Ubuntu, Mint} = 3个节点
连通分量2: {EeulerOS} = 1个节点

最大连通分量大小 = 3

优化技巧

1. 输入处理优化

// 可以在读入时直接处理连接关系
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        int val = sc.nextInt();
        if (val == 1 && i != j) {
            // 直接处理连接关系
            uf.union(i, j);
        }
    }
}

2. DFS递归深度优化

// 使用迭代版本的DFS避免栈溢出
private static int dfsIterative(int[][] isConnected, boolean[] visited, int start, int n) {
    Stack<Integer> stack = new Stack<>();
    stack.push(start);
    visited[start] = true;
    int size = 0;
    
    while (!stack.isEmpty()) {
        int node = stack.pop();
        size++;
        
        for (int i = 0; i < n; i++) {
            if (isConnected[node][i] == 1 && !visited[i]) {
                visited[i] = true;
                stack.push(i);
            }
        }
    }
    
    return size;
}

3. 并查集路径压缩优化

// 带路径压缩的查找操作
public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 路径压缩
    }
    return parent[x];
}

扩展应用

1. 朋友圈问题

这个算法可以直接应用于朋友圈问题：给定人员关系矩阵，求最大朋友圈的大小。

2. 网络连通性

在网络拓扑中，可以用来分析网络的连通性和找出最大的连通子网。

3. 社交网络分析

在社交网络中，可以用来找出最大的社交群体。

总结

三种解法都能正确解决问题，选择建议：

  1. DFS法：

    • 代码简洁，易于理解
    • 适合小规模数据
    • 推荐用于面试和学习

  2. BFS法：

    • 逻辑清晰，避免递归风险
    • 适合中等规模数据
    • 推荐用于实际应用

  3. 并查集法：

    • 专业的连通性解决方案
    • 适合大规模数据和动态更新
    • 推荐深入学习数据结构

核心要点：

  • 理解连通分量的概念和传递性
  • 掌握图遍历的基本方法（DFS/BFS）
  • 了解并查集这一重要数据结构
  • 注意邻接矩阵的对称性（无向图）

对于华为OD机试，建议优先掌握DFS法，因为它最直观易懂，代码量适中，且能很好地展示对图论基础概念的理解。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布