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×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},...,e_{n})
be a sequence of length n
of edges e_{i}∈ E
such that e_{i}=(v_{i},v_{i+1})
for a sequence of vertices (v_{1},...,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}→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., bottom(G)={v∈V∀w∈V:(v→w)⇒(w→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,...,v}
.
You may assume that 1<=v<=5000
.
That is followed by a nonnegative integer e
and, thereafter, e
pairs of vertex identifiers v_{1},w_{1},...,v_{e},w_{e}
with the meaning that (v_{i},w_{i})∈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
Rohit Agarwal:
20160701 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?


code_master5:
20160629 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


ayush:
20160629 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:


code_master5:
20160626 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:
20160626 19:04:21
@kshubham02: Your comment was really very helpful. Got my code accepted! Thank you! :) Last edit: 20160626 19:04:57 

code_master5:
20160625 20:10:46
@deerishi If u're suggesting this case:


deerishi:
20160625 01:19:56
Nice Problem. For those getting WA consider the case of a single vertex with a self loop. 

code_master5:
20160623 22:37:38
Please help me! I'm constantly getting WA. I've tried all the given testcases (including those in comments!!!). Help me find bugs in my last submission... 

kshubham02:
20160612 22:37:30
@Saumye Malhotra it looks like you haven't understood the question well. There is no concept of 'Multiple bottoms'. Please look at my reply to Abhishek Naik's comment. Hope it is helpful. Cheers :) 

kshubham02:
20160612 19:39:34
@Abhishek Naik You've got it wrong. In case 2, there's only one edge, going from 1>2. So, for 2, there are no nodes reachable from it. Hence it is a sink. For 1, there is one node reachable from it (2). However, from 2 you cannot reach back to 1. Hence, 1 is not a sink.

Added by:  Wanderley Guimarăes 
Date:  20070921 
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 