刷题笔记合集🔗

可以组成网络的服务器

问题描述

在一个机房中，服务器的位置标识在 的整数矩阵网格中， 表示单元格上有服务器， 表示没有。如果两台服务器位于同一行或者同一列中紧邻的位置，则认为它们之间可以组成一个局域网。

请你统计机房中最大的局域网包含的服务器个数。

输入格式

第一行输入两个正整数 和 ，。

之后为 的二维数组，代表服务器信息。

输出格式

最大局域网包含的服务器个数。

样例输入

2 2
1 0
1 1

样例输出

3

样例	解释说明
样例1	[0][0]、[1][0]、[1][1]三台服务器相互连接，可以组成局域网

数据范围

• 

题解

这道题目本质上是一个连通分量的计算问题。我们需要找出矩阵中所有连通的服务器集合，并返回最大集合的大小。

在矩阵中，两台服务器被认为是连通的，如果它们在同一行或同一列的相邻位置。这实际上定义了一个无向图，其中每个值为1的单元格是一个节点，两个节点之间有边当且仅当它们相邻且都是服务器。

解决这个问题的关键步骤是：

1. 遍历矩阵中的每个单元格
2. 当找到一个值为1的单元格（服务器）时，使用广度优先搜索(BFS)或深度优先搜索(DFS)找出所有与之连通的服务器
3. 计算连通分量的大小，并更新最大值
4. 将已经计算过的服务器标记为0，避免重复计算
5. 返回最大连通分量的大小

选择BFS而非DFS的原因是，在极端情况下（例如，矩阵接近最大尺寸100×100），DFS可能导致栈溢出。BFS使用队列而不是递归，避免了这个问题。

BFS的具体过程如下：

1. 从一个服务器开始，将其加入队列
2. 将该服务器标记为已访问（修改值为0）
3. 当队列不为空时，出队一个服务器
4. 检查该服务器上下左右四个方向的相邻单元格
5. 如果相邻单元格是服务器（值为1），则将其加入队列，并标记为已访问
6. 统计访问过的服务器数量，即为连通分量的大小

时间复杂度分析：

• 矩阵中每个单元格至多被访问一次，因此时间复杂度为O(n×m)
• 由于数据范围n,m≤100，最坏情况下需要处理10000个单元格，这个复杂度是可以接受的

通过这种方法，我们可以准确计算出最大的局域网包含的服务器个数。

参考代码

• Python

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

# 输入处理
n, m = map(int, input().split())
# 创建服务器矩阵
grid = [list(map(int, input().split())) for _ in range(n)]

# 定义四个方向的偏移
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# BFS函数用于找出所有连通的服务器
def find_network(r, c):
    # 如果当前位置不是服务器，直接返回0
    if grid[r][c] == 0:
        return 0
    
    # 初始化计数和队列
    cnt = 1
    grid[r][c] = 0  # 标记为已访问
    q = [(r, c)]
    
    # BFS搜索
    while q:
        x, y = q.pop(0)
        
        # 检查四个方向
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            
            # 检查边界和是否是服务器
            if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 1:
                cnt += 1  # 增加服务器计数
                grid[nx][ny] = 0  # 标记为已访问
                q.append((nx, ny))  # 添加到队列
    
    return cnt

# 主函数
def solve():
    max_size = 0
    
    # 遍历矩阵中的每个单元格
    for i in range(n):
        for j in range(m):
            # 如果找到服务器，计算网络大小
            if grid[i][j] == 1:
                net_size = find_network(i, j)
                max_size = max(max_size, net_size)
    
    return max_size

# 输出结果
print(solve())

• Cpp

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

// 定义四个方向的偏移量
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

int main() {
    int n, m;
    cin >> n >> m;
    
    // 读取服务器网格
    vector<vector<int>> grid(n, v