题目链接 二分图判定 题目描述 给定一张包含  个节点、 条无向边的图（不保证连通）。若存在一种黑白二色染色方式，使任意一条边的两个端点颜色不同，则该图为二分图。判断所给图是否为二分图。 输入：  第一行两个整数 、 接下来  行，每行两个整数 、 表示一条无向边  输出：  若该图为二分图，输出 Yes；否则输出 No  解题思路  对每个未染色的连通分量，任选一点开始 BFS/DFS 染色，使用两种颜色交替赋值。 遍历边时若发现相邻两点颜色相同，则不是二分图。 图可能不连通，需从每个未染色点启动一次搜索。 复杂度：。  代码   c++   java   python   #include...

题目链接 我朋友的朋友不是我的朋友 题目描述 共有  位成员，给出  对互为好友的关系（无向边）。记成员  的社牛指数为其好友数 ；朋友平均社牛指数为 。若 ，则称  为社牛。请按字典序输出所有社牛成员的姓名；若不存在，输出 None。 输入：  第一行两个整数 、 接下来  行，每行两个字符串 、 表示  与  互为好友  输出：  一行若干个字符串，按字典序升序输出所有社牛；若不存在仅输出 None  解题思路  将姓名离散化为编号，建无向图。 先统计每个成员的度数 ；再对每个成员求其邻居度数之和 。 判断条件等价于 （当  时无朋友，视为非社牛）。 将满足条件的姓名收集并按字典序排序输出...

题目链接 谍中谍中谍中谍中谍.... 题目描述 有  名学生，每名学生  指认一名学生 ，形成一张每点出度为  的有向图。老师从某个起点开始沿着指认关系不断抓下一位，第一次对某个已经被“警告”过的学生再次“警告”时，该学生自愿退学，过程结束。对每个可能的起点 ，求最终退学的学生编号。 输入：  第一行一个整数  第二行  个整数 ，其中  为学生  指认的学生  输出：  一行  个整数，第  个表示从  出发最终退学的学生编号  解题思路 功能图（每点出度为 ）由若干环及指向环的入树构成。对于任意起点 ：  若  在环上，则沿着环走一圈后第一次二次“警告”的是  自身，答案为 ； 若  不在...

题目链接 旺仔哥哥走迷宫 题目描述 给定一个包含  个房间、 条双向通道的迷宫，房间编号为 。第二行给出数组 ，当  表示房间  有陷阱、 表示安全。只能经过安全房间。判断是否存在一条仅经过安全房间的路径，从房间  到房间 。 输入：  第一行两个整数 、 第二行  个整数 （ 表示安全， 表示陷阱） 接下来  行，每行两个整数 、，表示  与  之间有双向通道  输出：  若存在路径，输出 Yes；否则输出 No  解题思路  建图（邻接表）。若起点或终点为陷阱，直接输出 No。 在只访问安全房间的前提下，对图做 BFS/DFS 可达性判定：从  出发扩展到所有安全邻居，检查能否到达 。 时...

题目链接 先序遍历、中序遍历和后序遍历 题目描述 给定一棵包含  个节点的二叉树，给出  条有向边 （父到子）。对子节点的左右关系规定：  若父节点拥有两个孩子，则编号较小者为左孩子，较大者为右孩子； 若父节点仅有一个孩子，且该子节点编号大于父节点编号，则视为左孩子；否则视为右孩子。  输出该二叉树的先序、中序、后序遍历序列。 输入：  第一行一个整数  接下来  行，每行两个整数 、 表示一条有向边   输出：  第一行：先序遍历序列；第二行：中序遍历序列；第三行：后序遍历序列。各行数字以单个空格分隔  解题思路  根据边构建每个节点的孩子集合；根节点为从未作为子节点出现的节点。 对每个父节...

题目链接 【模板】链式前向星 题目描述 给定一个无向图，包含  个点、 条边（点编号 ）。接下来给出  对  表示无向边。请输出每个点直接相连的点编号（邻接点），并按升序输出；若某点无邻接点，输出 None。 输入：  第一行两个正整数 、 接下来  行，每行两个整数 、 表示一条无向边  输出：  输出  行。第  行为与点  相邻的所有点的升序序列，空格分隔；若无相邻点输出 None  解题思路  使用链式前向星（压缩邻接表）存图：对每条无向边  分别向 、 的表头插入一条单向边。 为保证升序输出，对每个点 ，遍历其前向星链表收集邻居到临时数组，排序后输出。 总复杂度：收集合计 ，排序总代...

题目链接 【模板】整数域二分 题目描述 给定一个长度为  的数组 ，需要处理  次查询：每次给定区间 ，输出数组中满足  的元素个数。 输入：  第一行两个整数 、 第二行  个整数为数组  接下来  行，每行两个整数 、  输出：  对于每次查询，输出一个整数表示区间内元素的个数  解题思路 排序+二分模板：  先将数组  升序排序。 对于每个查询 ，答案为 ：   返回第一个不小于  的位置  返回第一个大于  的位置   二者差即为位于  的元素个数。  该做法是经典的整数域二分应用，预处理一次排序，单次查询二分两次。 代码   c++   java   python   #includ...

题目链接 时津风的资源收集 题目描述 共有四种资源：油、弹药、钢材、铝。每组数据给定目标资源量 。进入界面时四种资源初始均为 ，且任何时刻均需保持在区间 。每次操作可对单一资源进行以下之一：  将该资源  将该资源  将该资源  直接将该资源设为上限  直接将该资源设为下限   问使四种资源同时恰好达到目标所需的最少操作次数。 输入：  第一行一个整数  接下来  行，每行四个整数   输出：  对每组数据输出一个整数，表示最少操作次数  解题思路 四种资源相互独立，答案等于对四个目标分别计算最少步数再求和。设从  调到某一目标  的最少步数为 。  不使用“跳到上限”的情况下，只利用  调整...

题目链接 剪纸游戏 题目描述 给定一张由 '.' 与 '*' 组成的  矩阵，'.' 表示被剪去的小方格，'*' 表示仍保留的小方格。'.' 的每个连通块（按四方向连通）对应一个被剪下的图案。问被剪下来的图案中，有多少个是长方形（正方形视为特殊的长方形）。 输入：  第一行两个整数：、 接下来  行，每行一个长度为  的字符串，仅包含 '.' 与 '*'  输出：  一个整数，表示长方形图案的数量  解题思路 将每个 '.' 连通块视为一个图案，判断其是否为长方形：  用 BFS/DFS 在四方向（上下左右）上寻找 '.' 的连通块；统计该块的格子数 ，同时记录最小行、最大行、最小列、最大列，...

题目链接 没挡住洪水 题目描述 给定一个  的字符矩阵，'.' 表示已被洪水淹没的区域，'#' 表示空地。四联通的 '#' 组成一个区域。已知四条边界均为 '.'。洪水在接下来的一天会上涨：所有与 '.' 相邻（上下左右）的 '#' 都会被淹没。问上涨后有多少个 '#' 区域会被完全淹没。 输入：  第一行一个整数  接下来  行，每行一个长度为  的仅包含 '.' 与 '#' 的字符串  输出：  一行一个整数，表示将被完全淹没的空地区域数量  解题思路 设初始时的 '#' 连通块为一个区域。一天后，被淹没的仅是“与 '.' 相邻”的 '#'，且淹没是一次性的（不迭代传播）。因此一个区域会被...

题目链接 取数游戏 题目描述 给定  组数据。每组数据给出一个由非负整数构成的  数字矩阵。需要从矩阵中选出若干个数，使得任意两个被选中的位置在八连通意义下不相邻（即上下左右与四个对角方向均不能相邻）。求所有被选数字之和的最大值。 输入：  第一行一个正整数  对于每组数据：第一行两个正整数 、；接下来  行，每行  个非负整数  输出：  对于每组数据，输出一个非负整数，表示最大和  解题思路 将问题转化为“逐行状态压缩 DP”：  用长度为  的二进制掩码  表示一行中被选的位置； 合法需满足同一行内不相邻：。 跨行时，上一行掩码  与当前行掩码  应满足八连通不相邻：  垂直/重叠： 左...

题目链接 全排列 题目描述 给定一个整数 ，请按字典序输出数字  的所有排列。 输入：  一行一个整数   输出：  按字典序输出所有排列。每行输出  个整数，数字之间用单个空格分隔  解题思路 按字典序生成全排列有两种常见方法：  使用内置/标准库的“下一个排列”算法（next_permutation）。从初始数组  开始，循环输出并不断生成下一个排列，直到没有下一个排列。 使用回溯（DFS）：按从小到大的顺序依次选择未使用的数字，天然得到字典序。实现略长，但思路直观。  这里代码采用第一种方法实现（Python 使用 itertools.permutations，传入有序序列即可按字典序产...

题目链接 数水坑 题目描述 给定一个  的矩形网格，网格中的每个格子要么是水 W，要么是干地 .。若两个水格子在八连通（上下左右及四个对角方向）意义下互达，则属于同一个水坑。请计算水坑的数量。 输入：  第一行两个整数 、 接下来  行，每行一个长度为  的仅包含 W 与 . 的字符串  输出：  一行一个整数，表示水坑的数量  解题思路 本质是统计字符为 W 的连通块数量（八连通）。  枚举每个格子：当遇到未访问的 W，水坑数加一；随后以该格子为起点进行一次泛洪（BFS/DFS）将其所在连通块的所有 W 标记为已访问。 八个方向为 。 访问时需判越界与字符判断，仅扩展到值为 W 且未访问过的...

题目链接 迷宫寻路 题目描述 给定一个  的矩形迷宫。每个格子要么是空地 .，要么是墙 #。只能在空地间按上下左右四个方向移动。起点为左上角 ，终点为右下角 。判断是否存在一条路径从起点到终点。 输入：  第一行两个正整数 、 接下来  行，每行一个长为  的仅包含 . 与 # 的字符串，表示迷宫 保证起点与终点均为空地 .  输出：  若可以到达终点，输出 Yes；否则输出 No  解题思路 典型网格可达性判定。采用宽度优先搜索（BFS）或深度优先搜索（DFS）均可。这里给出 BFS：  用队列从起点 （以 0 基下标为 ）开始扩展 每次从队头取出格子，对四个方向  尝试前进 仅当新位置在边...