## BOTTOM - The Bottom of a Graph

no tags

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 non-negative 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 NIKHIL KUMAR SINGH: 2016-12-30 12:11:57 First Problem of SCC. Back in business again with this darshan_7807: 2016-12-30 09:06:46 3TLE, to 3 runtime error to AC :P and_roid: 2016-12-26 20:40:49 !!! Great question for SCC. !!! There can be more than 1 SCC that can act as a sink and "BOTTOM" is the collection of all these SCC(print in sorted order). !!! Try CAPCITY after this. Last edit: 2016-12-26 20:42:58 justforpractic: 2016-09-26 22:16:28 I've got WA and i don't why although i don't understand why case 3 3 1 2 2 1 3 must output 3 not 1 2 3 justforpractic: 2016-09-25 21:59:15 can any one explain to me how is 2 1 1 2 == 2 how is 2 sink ? ayush: 2016-07-13 19:12:59 @code_master5 i somehow figured it out later that day, anyways thanks for coming up. :) a simple SCC indeed. avisheksanvas: 2016-07-05 10:06:08 Simple SCC problem. The entire problem in one statement : (v→w)⇒(w→v)! And @codedecode0111 , the space at the end of each line does not matter! And for the order, if you do it the right way, it'll automatically be in Ascending Order! :) Last edit: 2016-07-05 10:09:31 Rohit Agarwal: 2016-07-01 17:42:03 Should we print is descending order or ascending order? The output says sorted order but doesn't specify which one. Are both valid? Can I get a WA if there's an extra space in the end of each line? EDIT: That was my mistake. Got AC. Make sure you sort them in ascending order and no spaces in the end of each line. Last edit: 2016-07-03 15:58:17 code_master5: 2016-06-29 17:28:04 @ayush because if a vertex u is directed towards another vertex v (i.e. u->v), where u and v belong to different SCCs, then 1. u definitely cannot belong to a sink ( or bottom) 2. every vertex belonging to the same SCC as u cannot belong to a sink because we know that u is connected to every other vertex in that SCC, and hence we can reach v from each of those vertices. for example, in your case, 1. 2->3 => 2 cannot be a sink 2. since 1->2 and 2->1 => (2,1) forms an SCC, and if we can reach 3 from 2, we can definitely reach 3 from 1 (via 2) Hope it helped!! ayush: 2016-06-29 16:09:49 if a vertex belongs to one component and has a neighbour of other component (by component i mean a SCC group), why the whole SCC group of that vertex is discarded, as given by test case: 3 3 1 2 2 1 2 3 0 output: 3 Please explain.Thanks in advance.