python算法练习题

最近看到了一道新题, 求助各位大神:

有n座大楼，编号从0到n-1。这些楼房之间相距甚远，从一个楼房到另一个楼房的唯一途径是乘坐公交车。

有m条公交线路。第i条（0 <= i < m）将你从u_i楼带到v_i楼（但不是反方向）。这些公交车运行非常频繁.

如果你从y楼到x楼最多可以乘坐两辆公交车，那么x楼就可以从y楼到达。什么是最方便的建筑？最容易到达的建筑可以从多少座建筑到达? 此外，列出所有最方便的建筑物.

Input

输入的第一行包含两个空格分隔的整数n和m，分别表示建筑物和公交线路的数量。

接着输入m行。第i行包含两个空间分隔的整数u_i和v_i，如上所述

Output

输出应该由两行组成。第一行应该包含一个单一的整数x，表示最容易进入的建筑物可以从哪些建筑物进入。

第二行应该包含一个最多为n个整数的列表，表示正好可以从x个建筑物中进入的建筑物的列表。按照递增的顺序列出这些建筑物。

C**traints

· 1 <= n <= 10000

· 0 <= u_i, v_i < n

· u_i != v_i (没有路线将建筑物与自己连接起来)

· 对于任何建筑物来说，最多只有70条公交线路以它为终点。

· 对m或路线没有额外的限制。

Time Limit

你的程序必须在9秒内完成对任何有效输入的运行。

Sample Input 1

6 5

0 1

1 2

2 3

3 4

4 5

Sample Output 1

3

2 3 4 5

Sample 1 Explanation

· 第一行表示有6栋楼和5条公交线路。

· 公交车路线在接下来的5行中有描述。例如，第二条线路带你从1号楼到2号楼。

· 0号楼只能从其自身进入。1号楼可以从0号楼和它本身进入。其余的建筑都可以从3个建筑中进入，包括它们自己。例如，2号楼可以通过自己、1->2和0->1->2到达，所以我们总共有三栋0、1和2号楼可以到达2号楼。3号楼可以通过自己，2->3，和1->2->3（最多两辆公交车）到达。所以我们总共有三栋楼1、2、3可以到达3号楼。

Sample Input 2

6 8

0 1

2 1

1 3

4 3

3 5

0 1

3 0

1 0

Sample Output 2

5

0 3