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
ayush:
20160713 19:12:59
@code_master5 i somehow figured it out later that day, anyways thanks for coming up. :) a simple SCC indeed. 

avisheksanvas:
20160705 10:06:08
Simple SCC problem. The entire problem in one statement : (v→w)⇒(w→v)!


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