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×V, its elements being called edges. Then G=(V,E) is called a directed graph.

Let n be a positive integer, and let p=(e1,...,en) be a sequence of length n of edges ei∈ E such that ei=(vi,vi+1) for a sequence of vertices (v1,...,vn+1). Then p is called a path from vertex v1 to vertex vn+1 in G and we say that vn+1 is reachable from v1, writing (v1→vn+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 non-negative integer e and, thereafter, e pairs of vertex identifiers v1,w1,...,ve,we with the meaning that (vi,wi)∈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: 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.

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:
Input:
1 1
1 1
my code gives
Output:
1
and I guess this is right!!!

deerishi: 2016-06-25 01:19:56

Nice Problem. For those getting WA consider the case of a single vertex with a self loop.

code_master5: 2016-06-23 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:2007-09-21
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