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 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

Added by:Wanderley Guimarăes
Date:2007-09-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:University of Ulm Local Contest 2003

hide comments
2014-12-07 00:22:06 ankipanki
Those who are getting wrong answer,
Input:
4 1
1 2
0
output:
2 3 4
2014-10-17 20:34:57 Divyank Duvedi
very nice question.....thumbs up :)
2014-09-22 13:53:31 lite_coder
Is the graph always connected?
2013-07-08 12:19:10 king
TLE with O(n^3),O(mn)

Last edit: 2013-07-08 15:01:58
2013-06-13 20:33:48 super human
learned a lot from this one..!!
2013-01-21 19:13:05 Tarun Gehlaut
@Alaa Shafaee: 2 doesnt have any out going edge. However you can always assume that a node has an edge to itself. so 2->2 is assumed. Hence 2 has been printed. as it is only linked to 2 and its imaginary image is linked to itself.
-> Haan ji Bilkul SAhi bola

Last edit: 2013-05-18 10:03:38
2012-12-24 06:22:55 Alaa Shafaee
I did not get the second test case. There is a path from 1 to 2, however, there is no path from 2 to 1 since we have 1 edge. Can someone explain it?
Thanks
2012-11-21 10:42:13 :D
Re: Paul. I hope so, but not sure. I think my sol didn't assume it. Since there's such spiffy math description, it would be a real blunder to mix a set with multiset.

Re Amit Ranjan:
It doesn't say that such a graph must exist. If you would manage to find it though, you'll know what to output ;)

Last edit: 2012-11-22 20:32:16
2012-11-21 01:33:01 Paul Draper
Since E is a subSET of VxV, that means there are no duplicate edges, right?
2012-10-29 19:53:57 aristofanis
@Amit Ranjan I think it can be proved that every graph has at least one sink.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.