题目
分析
这道题目的描述有点费解。我试着根据样本重新描述一下。
9 2
4 1 3 5 6
3 3 5 6 重点是两个车次的停靠信息。整理如下（Y表示明确停靠，N明确不停靠，?表示不知道）：
| 路线 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 1356 | Y | N | Y | N | Y | Y | ? | ? | ? |
| 356 | ? | ? | Y | N | Y | Y | ? | ? | ? |
题目中有一个隐含的条件：如果一个车站明确标明了N或者?，那么一定至少存在一趟车可以从某个明确停靠的车站去往那个车站——也就是需要换乘。如果一个站点需要多次换乘，那么它的重要性就不会高——这个和日常生活是一致的。
整合上两行给出的信息，可以看到，2/4/7/8/9都没有给出直达信息。但基于上述的隐含条件，无论从哪里到哪里，都只要换乘一次，也就是坐两趟车。比如：从2到6，可以2->3（隐含条件），然后3-6（已知条件）。所以，这些站点中，至少有2个层级（当然可能更多）。
再看第二个样本数据：
| 路线 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 1356 | Y | N | Y | N | Y | Y | ? | ? | ? |
| 356 | ? | ? | Y | N | Y | Y | ? | ? | ? |
| 159 | Y | N | N | N | Y | N | N | N | Y |
情况有点复杂了。如果要从2到8，需要：2->5（隐含条件）->9（隐含条件）->8（隐含条件）。也就是要至少换乘2次，这些站点中至少有3个层次。
至此，解题思路开始清晰：
- 读入一个车次，标记所有“停靠站”。
- 根据起点和终点，找到当中所有的“跳过站”。
- 对于每个“跳过站”，连上所有的“停靠站”(“来自站”，
outEdges，隐含条件），其“来自站”的inDegree（可以理解为它要为本站提供车次）加1。处理所有“跳过站”。以及所有车次。 - 用BFS方法进行路径搜索。
起点必然是那些inDegree==0的站，因为它们无法直达，只能转达。
- 遍历所有当前站点的出发点（必然是“停靠站”，存储在
outEdges），它的inDegree减一（有一趟车过来了，依赖关系减1），但换乘次数（level）要加1（转车次数多了一次）。但它可能由别的站点而来，所以还要取其最大值。 - 找到所有站点的最大
level。
答案
思考
这道题目，要搞清楚题意。懂了题意，才能有基本的解题思路。