🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 100+ 套笔试题，笔试真题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🌈 华子秋招笔试，来啦！！！

🍥 前两周出过一次 DFS 专场，华子这次直接来一次 BFS 专场，直呼好家伙

1️⃣ 二分图匹配的问题，数据范围比较小，每次可以直接暴力BFS check

2️⃣ BFS模拟，本次比较难写的一题，中途下车再上同一辆车不算，这个要分开考虑，细节也比较多

3️⃣ BFS模拟题，主要考验大家的代码基本功。

🧸 01.分组问题 评测链接🔗

题目描述

K小姐所在的公司要进行一次员工绩效互评。为了避免员工之间因为私交而给彼此高分，公司决定将员工分成两组，每组员工只能为另一组的员工打分。

现在已知公司共有 名员工，编号从 到 。同时给出一个二维数组 ，其中 包含了与员工 关系密切（例如是好友或者同一个项目组）的其他员工的编号。

请你帮助 K小姐设计一个算法，将这 名员工分成两组，使得每组内部不存在关系密切的员工。如果无法找到满足要求的分组方案，则输出 。

输入格式

第一行包含一个正整数 ，表示员工总数。

接下来 行，第 行包含若干个整数，表示 ，即与员工 关系密切的其他员工的编号。

输出格式

如果存在满足要求的分组方案，则输出两行，每行包含若干个整数，表示一个组内的员工编号。员工编号按从小到大的顺序输出，两组之间的顺序也按照第一个员工编号的大小关系排序。

方案内部也按照编号从小到大排序。输出排序最靠前的一种方案，如无法分成符合条件的两组，则输出

如输出如下两种方案时，选择第一种方案，因为方案一的分组第一个节点编号更小:

分组：
分组：

和

分组：
分组：

如输出如下两种方案时，选择第二种方案，因为方案二的分组第一个节点编号更小:

分组：
分组：

和

分组：
分组：

如果找不到满足要求的分组方案，则输出 。

样例输入1

4
1 3
0 2
1 3
0 2

样例输出1

0 2
1 3

样例输入2

4
1 2 3
0 2
0 1 3
0 2

样例输出2

-1

数据范围

• 
• 
• 中不会包含 ，也不会有重复元素
• 数据保证 是对称的，即如果 ，则

题解

BFS/二分图染色

这道题目本质上是一个图的二分图染色问题。可以将员工看作图中的节点，关系密切的员工之间连一条边。问题就转化为：能否将图中的节点分成两组，使得每条边的两个端点分别属于不同的组。

可以用 BFS 或者 DFS 来对图进行遍历和染色。这里选择使用BFS

具体步骤如下：

1. 构建邻接表来表示员工之间的关系。

2. 使用一个数组 color 来记录每个员工的分组情况。初始时，所有员工都未分组，用 -1 表示。

3. 对于每个未分组的员工，从他开始进行BFS：

   • 将他放入队列，并给他染色（比如用 0 表示第一组）
   • 不断从队列中取出员工，对于他的每个邻居（关系密切的员工）：
     • 如果邻居未染色，就给邻居染上相反的颜色，并将邻居加入队列
     • 如果邻居已经染色，检查颜色是否与当前员工相同。如果相同，说明无法二分，直接返回 -1

4. 如果BFS过程中没有发现冲突，就说明可以成功二分。我们将颜色为 0 的员工放入第一组，颜色为 1 的员工放入第二组。

5. 最后，需要按照题目要求对输出进行排序：

   • 两个组内部按员工编号从小到大排序
   • 两个组之间按第一个员工编号的大小关系排序

时间复杂度分析：构建邻接表的时间复杂度是 ，其中 是员工数， 是关系的总数。BFS的时间复杂度也是 。排序的时间复杂度是 。因此，总的时间复杂度是 。

参考代码

• Python

from collections import deque

def solve():
    # 读取输入
    n = int(input())
    graph = [[] for _ in range(n)]
    for i in range(n):
        relations = list(map(int, input().split()))
        graph[i] = relations

    # 初始化颜色数组，-1表示未染色
    color = [-1] * n

    # BFS函数
    def bfs(start):
        q = deque([start])
        color[start] = 0
        while q:
            u = q.popleft()
            for v in graph[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    q.append(v)
                elif color[v] == color[u]:
                    return False
        return True

    # 对每个未染色的节点进行BFS
    for i in range(n):
        if color[i] == -1:
            if not bfs(i):
                print(-1)
                return

    # 将节点分组
    group0 = [i for i in range(n) if color[i] == 0]
    group1 = [i for i in range(n) if color[i] == 1]

    # 对组内元素排序
    group0.sort()
    group1.sort()

    # 如果需要交换两组
    if group1 and (not group0 or group1[0] < group0[0]):
        group0, group1 = group1, group0

    # 输出结果
    print(*group0)
    print(*group1)

solve()

• Java

import java.util.*;

public class Main {
    static List<List<Integer>> graph;
    static int[] color;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符

        // 初始化图和颜色数组
        graph = new ArrayList<>(n);
        color = new int[n];
        Arrays.fill(color, -1);

        // 读取输入并构建图
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
            String[] relations = scanner.nextLine().split(" ");
            for (String r : relations) {
                graph.get(i).add(Integer.parseInt(r));
            }
        }

        // 对每个未染色的节点进行BFS
        for (int i = 0; i < n; i++) {
            if (color[i] == -1 && !bfs(i)) {
                System.out.println(-1);
                return;
            }
        }

        // 将节点分组
        List<Integer> group0 = new ArrayList<>();
        List<Integer> group1 = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (color[i] == 0) group0.add(i);
            else group1.add(i);
        }

        // 对组内元素排序
        Collections.sort(group0);
        Collections.sort(group1);

        // 如果需要交换两组
        if (!group1.isEmpty() && (group0.isEmpty() || group1.get(0) < group0.get(0))) {
            List<Integer> temp = group0;
            group0 = group1;
            group1 = temp;
        }

        // 输出结果
        printGroup(group0);
        printGroup(group1);
    }

    // BFS函数
    static boolean bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        color[start] = 0;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : graph.get(u)) {
                if (color[v] == -1) {
                    color[v] = 1 - color[u];
                    queue.offer(v);
                } else if (color[v] == color[u]) {
                    return false;
                }
            }
        }
        return true;
    }

    // 打印组
    static void printGroup(List<Integer> group) {
        for (int i = 0; i < group.size(); i++) {
            System.out.print(group.get(i));
            if (i < group.size() - 1) System.out.print(" ");
        }
        System.out.println();
    }
}

• Cpp

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

vector<vector<int>> graph;
vector<int> color;

// BFS函数
bool bfs(int start) {
    queue<int> q;
    q.push(start);
    color[start] = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : graph[u]) {
            if (color[v] == -1) {
                color[v] = 1 - color[u];
                q.push(v);
            } else if (color[v] == color[u]) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    int n;
    cin >> n;

    // 初始化图和颜色数组
    graph.resize(n);
    color.assign(n, -1);

    // 读取输入并构建图
    for (int i = 0; i < n; i++) {
        string line;
        getline(cin >> ws, line);
        int num;
        istringstream iss(line);
        while (iss >> num) {
            graph[i].push_back(num);
        }
    }

    // 对每个未染色的节点进行BFS
    for (int i = 0; i < n; i++) {
        if (color[i] == -1 && !bfs(i)) {
            cout << -1 << endl;
            return 0;
        }
    }

    // 将节点分组
    vector<int> group0, group1;
    for (int i = 0; i < n; i++) {
        if (color[i] == 0) group0.push_back(i);
        else group1.push_back(i);
    }

    // 对组内元素排序
    sort(group0.begin(), group0.end());
    sort(group1.begin(), group1.end());

    // 如果需要交换两组
    if (!group1.empty() && (group0.empty() || group1[0] < group0[0])) {
        swap(group0, group1);
    }

    // 输出结果
    for (int i = 0; i < group0.size(); i++) {
        cout << group0[i] << (i < group0.size() - 1 ? " " : "\n");
    }
    for (int i = 0; i < group1.size(); i++) {
        cout << group1[i] << (i < group1.size() - 1 ? " " : "\n");
    }

    return 0;
}

🌈 02.环保出行计划 评测链接🔗

问题描述

LYA 是一位热衷于环保的上班族。为了减少碳排放，她每天都选择乘坐公共交通工具上班。城市的公交系统由多条单向循环路线组成，每条路线都有固定的站点序列。例如，25 路公交的路线为 ，那么公交车会按照 的顺序循环行驶。

LYA 的日常通勤路线包括三个关键站点：最近的上车站、最喜欢的早餐店所在站点，以及离公司最近的下车站。她希望在保证买到早餐的前提下，用最少的换乘次数完成整个通勤过程。

你的任务是帮助 LYA 规划最优的乘车路线，使得她乘坐的公交车总数最少。需要注意的是，如果在同一条公交路线中下车再上车，仍然视为乘坐同一辆车。

输入格式

第一行包含 3 个整数 、、，分别表示 LYA 的上车站点编号、早餐店所在站点编号和下车站点编号。

第二行包含一个整数 ，表示公交路线的数量。

接下来的 行，每行描述一条公交路线。每行的第一个整数 表示该路线的站点数量，后面跟着 个整数，表示该路线经过的站点编号（按顺序排列）。

输出格式

输出一个整数，表示 LYA 需要乘坐的公交车数量的最小值。如果无法找到满足条件的路线，输出 。

样例输入 1

1 3 5
4
3 1 2 6
3 2 3 7
3 5 6 8
2 5 7

样例输出 1

3

样例解释 1

LYA 可以按以下路线行进：

1. 在站点 1 乘坐第一条路线的公交车。
2. 在站点 2 下车，换乘第二条路线的公交车。
3. 在站点 3 下车购买早餐，然后继续乘坐第二条路线的公交车。
4. 在站点 7 下车，换乘第四条路线的公交车。
5. 最终在站点 5 下车到达公司。

总共乘坐了 3 辆不同的公交车（），因此输出 3。

样例输入 2

1 3 4
2 
3 1 2 4
3 3 5 6

样例输出 2

-1

样例解释 2

LYA 只能乘坐第 1 条公交路线上车，但无法通过该路线的站台换乘到第 2 条公交路线购买早餐，因此没有匹配的路线，返回 -1。

样例输入 3

4 19 28
5
5 3 4 7 8 10
6 10 12 16 19 27 28
4 5 7 11 17
4 17 19 22 23
3 23 27 28

样例输出 3

2

样例解释 3

LYA 可以选择 的公交路线，乘坐的公交车总数为 2。虽然也可以选择 的公交路线，但这样需要乘坐 4 辆公交车。因此，最佳的乘车路线是 ，结果为 2。

数据范围

• 公交路线数量 的范围：。
• 公交站台编号的范围：。
• 每条公交路线经过的站台数量范围：。
• 保证起点站台、早餐站点和终点站台互不相同。
• 每条路线中的站台编号按升序排列，且不包含重复的站台。

题解

两次BFS+思维

关键点在于理解题目的特殊规则：在早餐店换乘同一辆车不算额外的换乘次数。这就好比在早餐店门口下车，买完早餐后又坐回同一辆车，这种情况下不需要额外付车费。

解决这个问题的思路其实很直观。首先，从起点出发，找到到达早餐店的最短路径。然后，从早餐店出发，找到到达公司的最短路径。这两段路径加起来就是整个旅程的最优解。

具体来说，可以使用两次（BFS）来实现：

1. 第一次BFS：从起点到早餐店。
2. 第二次BFS：从早餐店到公司。

在第二次BFS中，需要特别注意处理在早餐店的特殊换乘规则。如果某条路线经过早餐店，那么在这条路线上继续前进不需要增加换乘次数。

举个例子，假设有以下公交路线：

1号线：1 -> 2 -> 3 -> 4
2号线：2 -> 5 -> 6
3号线：4 -> 5 -> 7

起点在1，早餐店在4，终点在7。

第一次BFS会得到路径：1 -> 2 -> 3 -> 4（1号线），换乘次数为0。 标记1号线为包含早餐店的路线。

第二次BFS时，从4出发：

• 可以直接使用1号线到达其他站点，不增加换乘次数。
• 使用3号线时需要增加换乘次数。

最终路径可能是：1 -> 2 -> 3 -> 4（1号线）-> 5 -> 7（3号线），总换乘次数为 1。

参考代码

• Python

from collections import deque

MAX_STATIONS = 1000005  # 最大站点数
MAX_ROUTES = 505  # 最大路线数

# 初始化全局变量
dist_to_breakfast = [0] * MAX_STATIONS  # 存储从起点到每个站点的距离
dist_from_breakfast = [0] * MAX_STATIONS  # 存储从早餐店到每个站点的距离
visited = [0] * MAX_STATIONS  # 用于BFS中标记已访问的路线
breakfast_route = [0] * MAX_ROUTES  # 标记哪些路线包含早餐店
route_first_visit = [0] * MAX_ROUTES  # 记录每条路线首次被访问的时间
station_to_routes = [[] for _ in range(MAX_STATIONS)]  # 存储每个站点所属的路线
routes = []  # 存储每条路线经过的站点

def bfs_to_breakfast(start, breakfast):
    q = deque([start])
    dist_to_breakfast[start] = 1  # 起点距离设为1
    while q:
        current = q.popleft()
        for route in station_to_routes[current]:
            if not visited[route]:
                route_first_visit[route] = dist_to_breakfast[current] + 1
                for station in routes[route]:
                    if not dist_to_breakfast[station]:
                        dist_to_breakfast[station] = dist_to_breakfast[current] + 1
                        q.append(station)
                visited[route] = 1  # 标记路线为已访问
    
    # 标记包含早餐店的路线
    for i in range(1, len(routes)):
        if route_first_visit[i] == dist_to_breakfast[breakfast]:
            if breakfast in routes[i]:
                breakfast_route[i] = 1

def bfs_from_breakfast(breakfast, end):
    global visited
    visited = [0] * MAX_STATIONS  # 重置visited数组
    q = deque([breakfast])
    dist_from_breakfast[breakfast] = 1  # 早餐店距离设为1
    while q:
        current = q.popleft()
        for route in station_to_routes[current]:
            if not visited[route]:
                distance = dist_from_breakfast[current] + 1
                if breakfast_route[route]:
                    distance -= 1  # 如果是包含早餐店的路线，不增加换乘次数
                for station in routes[route]:
                    if not dist_from_breakfast[station]:
                        dist_from_breakfast[station] = distance
                        q.append(station)
                visited[route] = 1  # 标记路线为已访问

def solve():
    # 读取输入
    start, breakfast, end = map(int, input().split())
    num_routes = int(input())
    global routes
    routes = [[] for _ in range(num_routes + 1)]  # 路线编号从1开始
    for i in range(1, num_routes + 1):
        route = list(map(int, input().split()))
        routes[i] = route[1:]  # 第一个数字是站点数量，跳过
        for station in routes[i]:
            station_to_routes[station].append(i)
    
    # 执行从起点到早餐店的BFS
    bfs_to_breakfast(start, breakfast)
    if not dist_to_breakfast[breakfast]:
        print(-1)  # 无法到达早餐店
        return
    
    # 执行从早餐店到终点的BFS
    bfs_from_breakfast(breakfast, end)
    if not dist_from_breakfast[end]:
        print(-1)  # 无法到达终点
        return
    
    # 计算并输出结果
    print(dist_to_breakfast[breakfast]+ dist_from_breakfast[end] - 2)

solve()  # 执行主函数

• Java

import java.util.*;

public class Main {
    static final int MAX_STATIONS = 1000005;  // 最大站点数
    static final int MAX_ROUTES = 505;  // 最大路线数

    // 初始化全局变量
    static long[] dist_to_breakfast = new long[MAX_STATIONS];  // 存储从起点到每个站点的距离
    static long[] dist_from_breakfast = new long[MAX_STATIONS]