宠物领养算法https://www.zbrczp.cn\n先为每种毛色 (1 ~ 3) 建一个小根堆，元素为 (编号, idx)，并把每只宠物同时按两种毛色各压入对应堆。这样堆顶永远保持当前颜色下“编号最小”的候选。再准备一个布尔数组 adopted[idx] 记录是否已被领养。每来一个领养人，只需查看他偏好颜色 c 的堆：不停地把堆顶弹掉，直到堆空或遇到第一只 未 被领养的宠物——这只就是答案。若堆空说明无符合宠物，输出 ‑1；否则输出编号并将 adopted[idx] = true。因为每只宠物只会被成功弹出一次，且在被别人领走之前至多被“白弹”一次，所以总体弹出≤ 2n 次，建堆与所有操作的时间复杂度为 O((n + m) log n)；只用到 3 个堆和两个长度为 n 的数组，空间 O(n)。https://www.zbrczp.cn\n独立匹配判定算法https://www.zbrczp.cn\n独立匹配需满足：① 边集内部任意两边不共享顶点；② 图中任意其他边，顶点与边集重叠不能超过 1 个。对每次查询引入自增时间戳 timer，借助两个整型数组避免每轮清零：vtag[1..n] 记录顶点是否在本次边集中出现，etag[0..m−1] 记录边是否属于本次边集。遍历查询边集：若某边的两个端点已有任一点在 vtag 上被标过，直接判为非法；否则把这条边和它的两个端点都打上当前 timer 标签。若第一阶段无冲突，再线性扫描全部 m 条边：只要发现一条“不在边集且两端点都已出现在 vtag 中”的边，说明它与边集中某条边同时共享两个端点，违反条件②。两轮检查都通过才输出 “Yes”，否则 “No”。每次查询最多扫描一次全集边，故时间复杂度 O(m)，空间 O(n + m)；利用时间戳技术把数组复位成本降为 O(1)。https://www.zbrczp.cn\n总的来说没那么难 但是需要有长期学习算法的经历才能写出#秋招笔试
