华为4.12实习机试第三题求解题思路

3、水资源调度
一座山峰按高度分为N层，从高到低编号分别为0，1，……，N-1除最低层外每一层上都有一个蓄水池，通过若干管道将每一层蓄水池中的水输送至最低层的水库中，管道之间通过阀门连接(阀门总数为M)，现要找到每一层中离水库最近的关键阀门。
某一层的关键阀门定义为从该层蓄水池流向水库的水要么经过该阀门目不全部流向更低层(不考虑水库层)关键阀门，或者不经过该阀门目必须经过更低层(不考虑水库层)的关键阀门。
即:第n(n<N-2)层的关键阀门为kn，从n层蓄水池流向水库的水如果流经kn，则必须存在流经kn的水未流经任何ki(n<<=N-2)，如果未流经kn，则至少流经一个ki(n< i<=N-2)。其中，第N-2层的关键阀门为kN-2，必须使得所有从第N-2层蓄水池流向水库的水全部经过kN-2.
关键阀门有如下性质:
1.任何路径从蓄水池流向水库的水，都必须经过至少一个关键阀门;
2.关键阀门从底层向上层确定，每层只有至多一个关键阀门
3.如果一层中从蓄水池流向水库的水全部流经了更低层的关键阀门，则该层无关键阀门;
4.如果一层中有多个阀门符合要求，则更靠近水库的确定为关键阀门;
5.水库层无关键阀门。

输入
第一行:输入两个整数N和M，其分别表示层数与阀门总数。
如3,5代表共有3层，5个阀门。
第二行:输入M个数字表示ID为0到M-1的阀门所在层数，层数为递增顺序。
如 0 0 1 1 2代表编号为0-4的阀门所在层数。0,1阀门在第0层，2,3阀门在第1层，4号阀门在第2层。
接下来输入M行，第行中的第一个数字k;表示通过阀门i-1下一步可到达的阀门个数。该行后面的 ki个数字分别表示这些阀门的编号ID，若k;为0则表示下一步没有可到达的阀门。
如
2 1 2
1 3
1 3
1 4
0，
分别表示0号阀门有2个可流向的阀门分别为1号阀门和2号阀门:1号阀门有1个可流向的阀门为3号阀门:2号阀门有1个可流向的阀门为3号阀门:3号阀门有一个可流向的阀门为4号阀门;4号阀门没有可流向的阀门;
注:最后一层有且只有一个阀门连接到水库，不同层中水只能由高层流向低层，同一层中水只能由小ID的阀门流向大ID的阀门。每层的最小ID的阀门只能接收来自该层蓄水池的水。
其中，1≤M≤2000，1≤N≤200≤ki<M