传送门失败了……ㄒoㄒ
Description
给出一张有 n 个点的无向图和长为 n 的序列 a ，请给出一种方案以选择部分的点或不选。设
bi
表示“和
i
点有连边的点和且被选择的数目”。使得 ∀i,ai≠bi 的前提下，给出一种合法方案。（本题支持 SPJ ）
Solution
考虑构造一种合法方案。
从特殊情况出发。
若当前所有
ai≠0
则不必新加入点即可满足要求反之，找到第一个
ai=0
并选择
i
加入方案
若存在边
(i,j) 则
aj
减一。回到步骤一，检查当前方案合法性。
证明
不合法情况仅限 所有点已加入方案
∃ai=0
与“当且仅当
ai=0
时将
i
<script type="math/tex" id="MathJax-Element-48">i</script> 加入队列” 策略 矛盾。
故不存在这种情况，得证。
“找不到代码”
