JZOJ2018.07.12【2018提高组】模拟B组 挑竹签

JZOJ2018.07.12【2018提高组】模拟B组 挑竹签

4269. 【NOIP2015模拟10.27】挑竹签 

题目描述

挑竹签——小时候的游戏
夏夜，早苗和诹访子在月光下玩起了挑竹签这一经典的游戏。
挑竹签，就是在桌上摆上一把竹签，每次从最上层挑走一根竹签。如果动了其他的竹签，就要换对手来挑。在所有的竹签都被挑走之后，谁挑走的竹签总数多，谁就胜了。
身为神明的诹访子自然会让早苗先手。为了获胜，早苗现在的问题是，在诹访子出手之前最多能挑走多少竹签呢？

为了简化问题，我们假设当且仅当挑最上层的竹签不会动到其他竹签。

输入

第一行输入两个整数n,m, 表示竹签的根数和竹签之间相压关系数。
第二行到m+1 行每行两个整数u,v，表示第u 根竹签压住了第v 根竹签

输出

一共一行，一个整数sum，表示最多能拿走sum 根竹签。

样例输入

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

样例输出

3

样例解释：
一共有6 根竹签，其中1 压住2，2 压住3，3 压住1，4 压住3 和5，6 压住5。最优方案中，我们可以依次挑走4、6、5 三根竹签。而剩下的三根相互压住，都无法挑走。所以最多能挑走3 根竹签。

其实这道题挺简单的，宽搜一下就行了（可怜我比赛打深搜标记超时）。

先把所有点的入度算出来，然后将入度为0的点加入宽搜队列并更新答案

将队列头指针指向的点能到达的点枚举一遍（链式前向星），将这些边给删掉，即给能到达的点入度减一，再判断它的入度是否为零，为0则加入队列，重复操作，并更新答案。

证明很简单，因为没有入度的点是不可能在环内的，将没有入度的点给删掉，又会出现新的没有入度的点，如果到之后有点的入度仍然不为0，要不就是因为在环中，要不就是因为某个可以到达它的点在环中。