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

Sample Output

1 3

hide comments
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?

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
Please explain.Thanks in advance.

code_master5: 2016-06-26 21:56:03

Finally! I got ac.. But I was getting WA when I was using low[] values as id for an SCC (yeah! u guessed right, I was using Tarjan's Algo for finding SCC). I was assuming that low value will be different for each SCC. Can anyone explain where I went wrong!!!

Abhishek Naik: 2016-06-26 19:04:21

@kshubham02: Your comment was really very helpful. Got my code accepted! Thank you! :)

Last edit: 2016-06-26 19:04:57
code_master5: 2016-06-25 20:10:46

@deerishi If u're suggesting this case:
1 1
1 1
my code gives
and I guess this is right!!!

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