问题2084--图的底部(POJ2553)

2084: 图的底部(POJ2553)

时间限制: 1 Sec  内存限制: 128 MB
提交: 8  解决: 8
[提交] [状态] [讨论版] [命题人:]

题目描述

对于有向图G 中任意一个节点v ,如果节点v 可以到达节点w ,那么节点w 都可以到达节点v ,那么节点v是一个sink节点。图G 的底部是由图G 中所有的sink节点构成的,请按顺序输出图G 底部的所有sink节点,如果没有sink节点,则输出一个空行。

输入

输入包含几个测试用例,每个测试用例都对应一个有向图G 。每个测试用例都以整数v (1≤v ≤5000)开始,表示图G 的节点数,节点编号为1~v 。接下来是非负整数e ,然后是e 对节点编号v 1 ,w 1 ,…,ve ,we ,其中(vi ,wi )表示一条边。在最后一个测试用例后跟着一个0。

输出

单行输出图底部的所有sink节点。如果没有,则输出一个空行。

样例输入 Copy

3 3
1 3 2 3 3 1
2 1
1 2
0

样例输出 Copy

1 3
2

来源/分类