题目链接 二分图判定 题目描述 给定一个包含  个节点和  条边的无向图。如果能将图中的节点染成黑白两种颜色，使得每条边的两个端点颜色都不同，那么这个图就被称为二分图。 任务是判断给定的图是否为二分图。 解题思路 判断一个图是否为二分图的经典方法是染色法。一个图是二分图，当且仅当它不包含任何奇数长度的环。我们可以通过图遍历（如广度优先搜索 BFS 或深度优先搜索 DFS）来模拟这个染色过程。 算法的核心思想是：尝试用两种颜色（例如，颜色 1 和颜色 2）对图中的节点进行染色。从任意一个未被染色的节点开始遍历，将其染成颜色 1。然后，将其所有相邻的节点染成颜色 2。再将与颜色 2 的节点相邻的未...

题目链接 我朋友的朋友不是我的朋友 题目描述 在一个社交圈中，有  位成员和  对朋友关系。每位成员的“社牛指数”定义为其直接认识的朋友数量。而“朋友平均社牛指数”则定义为其所有朋友的“社牛指数”的算术平均值。 如果一个成员的“社牛指数”大于其“朋友平均社牛指数”，则称该成员为“社牛”。 任务是找出这个社交圈里所有的“社牛”，并按字典序升序输出他们的名字。 解题思路 这是一个图论问题，我们可以将成员看作图的节点，朋友关系看作无向边。问题的核心是计算每个节点的两个关键指标：度（社牛指数）和邻居节点的平均度（朋友平均社牛指数）。 由于成员的名字是字符串，直接用字符串作为图的节点索引不方便，因此我们...

题目链接 谍中谍中谍中谍中谍.... 题目描述 有  名学生（编号  到 ），每位学生  都会指认一名学生  作为带头人。老师从任意一名学生开始警告，然后根据指认关系一路警告下去，直到第一次遇到一名已经被警告过的学生。这名被重复警告的学生将被劝退。 任务是，对于每个可能的起始学生 （从  到 ），找出最终被劝退的学生是谁。 解题思路 这个问题可以被模型化为一个函数图（functional graph）。在这张图中，每个节点（学生）都恰好有一条出边（指向其指认的学生）。这种图的结构特点是，它由一个或多个互不相连的组件构成，而每个组件都包含一个有向环，以及一些指向这个环的树状结构。 当老师从一个学...

题目链接 鞋带难题 题目描述 俱乐部聚会上共有  名学生，用  根鞋带将若干学生两两捆绑，每根鞋带连接恰好两名学生。 管理员按以下流程反复清场：  对所有学生统计其当前捆绑人数（即当前度数）。 把所有度数为 1 的学生记录下来；若无此类学生则流程结束。 将这批记录学生作为一组踢出俱乐部，并连同与他们相连的鞋带一起带走。  流程可能重复多次。求最终一共踢出了多少组学生。 解题思路 这个问题可以被抽象成一个图论问题。 名学生可以看作是图中的  个节点， 根鞋带则是连接节点的  条无向边。一个学生的“捆绑人数”就是图中对应节点的度。 题目描述的清场流程本质上是一个不断“剥离”图中度为 1 的节点的过...

题目链接 旺仔哥哥走迷宫 题目描述 在一个由  个房间和  条双向通道组成的迷宫中，旺仔哥哥需要从房间  找到通往房间  的出口。部分房间设有陷阱，由一个数组  标记，若  则房间  有陷阱，若  则房间安全。旺仔哥哥只能在安全的房间内移动。判断是否存在一条仅经过安全房间的路径。 解题思路 本题可以抽象为一个图论问题：给定一个图，判断两个节点（房间  和房间 ）之间是否存在一条路径，使得路径上的所有节点都满足特定条件（安全）。 这是一个典型的图遍历问题，可以使用广度优先搜索 (BFS) 或深度优先搜索 (DFS) 来解决。这里我们选用 BFS，因为它可以找到最短路径，虽然本题只要求判断路径是否...

题目链接 图的分类 题目描述 给定一个包含  台计算机和  条网线的连通网络。判断该网络的拓扑结构是链型 (line)、环型 (ring)、星型 (star)，还是不属于以上三类的未知结构 (unknown)。 解题思路 本题的核心是根据图中节点的度数分布来对图进行分类。一个节点的“度”是指与该节点直接相连的边的数量。由于题目保证图是连通的，我们可以通过统计所有节点的度数，来总结出每种特定结构的独有特征。 1. 结构特征分析   链型 (line):   一条链有  个节点，必然有  条边。   度数分布：恰好有两个度为  的节点（链的两端），以及  个度为  的节点（链的中间部分）。    ...

题目链接 小红的树上游戏 题目描述 在一棵  个节点的无根树上，小红和朋友轮流删除叶子节点。若某位玩家删除了一个特殊的节点 ，则该玩家立即获胜。双方都采取最优策略，小红先手，判断她是否必胜。 解题思路 本题是一个博弈问题。由于双方都采取最优策略，我们需要找到决定游戏胜负的根本性质。 1. 直接获胜条件 游戏最简单的情况是，特殊节点  在游戏开始时就是一个叶子节点（度数为），或者是一个孤立点（度数为，当  时）。在这种情况下，小红作为先手，可以在她的第一个回合直接删除节点  并获胜。因此，这是一个必胜条件。 2. 游戏过程分析 如果节点  的初始度数大于，游戏将继续。双方轮流移除叶子节点。   ...

题目链接 先序遍历、中序遍历和后序遍历 题目描述 给定一棵包含  个节点的二叉树，以  条有向边 （父节点指向子节点）的形式给出。子节点的左右关系需要根据以下规则确定：   若父节点有两个孩子，编号较小者为左孩子，较大者为右孩子。   若父节点只有一个孩子：  若子节点编号大于父节点编号，则该孩子为左孩子。 否则（子节点编号小于父节点编号），该孩子为右孩子。    你需要输出该二叉树的先序、中序、后序遍历序列。 解题思路 本题的解法分为两个主要步骤：1. 重建二叉树结构 和 2. 执行标准遍历。 1. 重建二叉树 首先，我们需要根据输入的父子关系和给定的左右孩子规则，构建出完整的二叉树。   ...

题目链接 上司的舞会 题目描述 公司有  名员工，构成一个多棵树组成的森林结构（即层级关系）。每位员工要么是最高层（没有上司），要么有且仅有一位直接上司。需要将所有员工分到若干小组，要求同一个小组内的任意两名员工之间不能有直接或间接的上级关系。求满足该条件的最小小组数量。 解题思路 这道题的核心在于理解分组的约束条件。 核心约束 “同一小组内不得出现任何一对员工具有上级关系。” 这句话是解题的关键。让我们考虑一条从上到下的指挥链，例如：A 是 B 的上司，B 是 C 的上司。  A 和 B 不能在同一组。 B 和 C 不能在同一组。 A 和 C也不能在同一组（因为 A 是 C 的间接上司）。 ...

题目链接 求树的根 题目描述 给定一棵包含  个节点的有根树，节点编号从 1 到 。输入以  条有向边 u -> v 的形式给出。你需要找出并输出：  树的根节点编号。 所有叶子节点的编号，并按升序排列。  解题思路 这道题的本质是利用图论中节点度 (degree) 的概念来识别树的特定部分。题目以有向边的形式给出了树的结构，这为我们提供了清晰的方向。 核心定义  入度 (In-degree)：指向一个节点的边的数量。 出度 (Out-degree)：从一个节点出发的边的数量。  根据有根树的性质，我们可以得出以下结论：  根节点：是树的唯一源头，没有其他节点指向它。因此，根节点的入度为...

题目链接 【模板】链式前向星 题目描述 给定一个包含  个点、 条边的无向图。点的编号从 1 到 。你需要对于每个点，升序输出其所有直接相连的点的编号。如果一个点没有任何邻居，则输出 "None"。 解题思路 本题的本质是图的存储与遍历。我们需要一种数据结构来表示图，然后遍历这个结构来找到每个点的所有邻居。 在 C++ 中，最直接的方法是使用 std::vector<std::vector<int>> adj，其中 adj[i] 存储了节点  的所有邻居。然而，在传统的算法竞赛中，链式前向星是一种更常用、空间效率更高、且在某些情况下遍历速度更快的静态...

题目链接 小红的皇后 题目描述 在一个  的棋盘上，有一些格子是障碍物(*)，其余为空格(.)。一个皇后从左上角  出发，目标是到达右下角 。皇后每次移动可以沿右、下、右下三个方向之一前进任意多格，且移动路径上不能有障碍物。求从起点到终点的最少移动步数。 解题思路 本题可以看作一个最短路径问题，但由于边的权重特殊（每次移动，无论多远，成本都是1），使用动态规划是解决此类问题的经典方法。 核心思想 问题的核心在于，沿同一个方向连续移动不增加步数，但转换方向则需要增加一步。这启发我们，DP的状态不仅要记录位置，还必须记录是“通过哪种方向的移动”到达该位置的。 动态规划设计   状态定义:  表示到...

题目链接 太阳系DISCO 题目描述 在一个由  个行星构成的环形星系中，行星顺时针编号为  到 （ 为偶数）。你从起点行星  出发，目标是到达终点行星 。你有以下三种移动方式，每种都消耗 1 单位时间：  顺时针移动  颗行星。 逆时针移动  颗行星。 传送：顺时针移动  颗行星（即跳到正对面）。此技能最多使用  次。  请求出从  到  的最少时间。如果无法到达，输出 -1。 解题思路 这是一个在带有资源限制（传送次数）的图上求最短路径的问题。由于每次操作的成本都是 1，广度优先搜索 (BFS) 是最合适的算法。 核心思想：双层图模型 问题的关键在于如何处理传送技能和其次数限制。一个传送操...

题目链接 时津风的资源收集 题目描述 玩家有四种资源，初始值均为 10。给定四种资源的目标量 。玩家可以对任意一种资源执行以下操作，但必须保证资源量始终在  的区间内：  资源量 。 资源量 。 资源量 。 直接将资源量设为上限 。 直接将资源量设为下限 。  每种操作计为一次。求使四种资源量同时达到目标值所需的最少总操作次数。 解题思路 本题的核心是计算将四种资源从初始值 10 变为目标值所需的最少操作次数。由于对每种资源的操作是相互独立的，我们可以将问题分解为四个相同的子问题：计算单一资源从 10 变为目标值  所需的最少操作次数。最终答案是这四个子问题解的和。 对于单一资源，问题可以抽象...