BOTTOM  The Bottom of a Graph
We will use the following (standard) definitions from graph theory. Let $V$ be a nonempty and finite set, its elements being called vertices (or nodes). Let $E$ be a subset of the Cartesian product $V \times V$, its elements being called edges. Then $G = (V, E)$ is called a directed graph.
Let $n$ be a positive integer, and let $p = (e_1, \ldots, e_n)$ be a sequence of length $n$ of edges $e_i \in E$ such that $e_i = (v_i, v_{i+1})$ for a sequence of vertices ($v_1, \ldots, v_{n+1}$). Then $p$ is called a path from vertex $v_1$ to vertex $v_{n+1}$ in $G$ and we say that $v_{n+1}$ is reachable from $v_1$, writing $(v_1 \to v_{n+1})$.
Here are some new definitions. A node $v$ in a graph $G = (V, E)$ is called a sink, if for every node $w$ in $G$ that is reachable from $v$, $v$ is also reachable from $w$. The bottom of a graph is the subset of all nodes that are sinks, i.e., $\mathrm{bottom}(G) = \{v \in V \mid \forall w \in V : (v \to w) \Rightarrow (w \to v) \}$. You have to calculate the bottom of certain graphs.
Input Specification
The input contains several test cases, each of which corresponds to a directed graph $G$. Each test case starts with an integer number $v$, denoting the number of vertices of $G = (V, E)$, where the vertices will be identified by the integer numbers in the set $V = \{1, \ldots, v\}$. You may assume that $1 \le v \le 5000$. That is followed by a nonnegative integer $e$ and, thereafter, $e$ pairs of vertex identifiers $v_1, w_1, \ldots, v_e, w_e$ with the meaning that $(v_i, w_i) \in E$. There are no edges other than specified by these pairs. The last test case is followed by a zero.
Output Specification
For each test case output the bottom of the specified graph on a single line. To this end, print the numbers of all nodes that are sinks in sorted order separated by a single space character. If the bottom is empty, print an empty line.
Sample Input
3 3 1 3 2 3 3 1 2 1 1 2 0
Sample Output
1 3 2
hide comments
varun yadav:
20160125 11:19:37
cake walk :) simple scc problem 

Deepak :
20160124 18:48:57
nice one..AC in one go.. 

kejriwal:
20151216 19:46:20
nice one !! 

Saumye Malhotra:
20151024 10:35:27
What is to be done when a graph has multiple bottoms?do we have to print the nodes of bottom with maximum size? If yes, in second case there are two bottoms both of size 1, why is only 2 printed.


Kushal Saharan:
20151021 06:35:31
For people getting WAs, please keep in mind that reachability doesn't mind the vertices have to be directly connected. Overlooking this costed me 2 WAs. 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20150818 17:34:28
My first solved SCC problem on dirrected graph ;) learned something new :D 

badry atef:
20150805 15:26:40
a very nice SCC problem :) 

Medo:
20150805 13:19:05
It's impossible for a graph to have no sink nodes. Don't account for that case if you are getting a WA. 

Ankit Kumar:
20150716 21:07:13
O(V+E) solution > AC


i_am_looser:
20150606 21:27:19
Good question..... learnt something useful 
Added by:  Wanderley Guimarăes 
Date:  20070921 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 
Resource:  University of Ulm Local Contest 2003 