BOTTOM - The Bottom of a Graph
We will use the following (standard) definitions from graph theory.
V be a nonempty and finite set, its elements being called vertices (or nodes).
E be a subset of the Cartesian product
V×V, its elements being called edges.
G=(V,E) is called a directed graph.
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
p is called a path from vertex
v1 to vertex
G and we say that
vn+1 is reachable from
Here are some new definitions.
v in a graph
G=(V,E) is called a sink, if for every node
G that is reachable from
v is also reachable from
The bottom of a graph is the subset of all nodes that are sinks, i.e.,
You have to calculate the bottom of certain graphs.
The input contains several test cases, each of which corresponds to a directed graph
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
You may assume that
That is followed by a non-negative integer
e and, thereafter,
e pairs of vertex identifiers
v1,w1,...,ve,we with the meaning that
There are no edges other than specified by these pairs.
The last test case is followed by a zero.
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.
3 3 1 3 2 3 3 1 2 1 1 2 0
1 3 2
Should we print is descending order or ascending order? The output says sorted order but doesn't specify which one. Are both valid?
@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
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:
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!!!
@kshubham02: Your comment was really very helpful. Got my code accepted! Thank you! :)Last edit: 2016-06-26 19:04:57
@deerishi If u're suggesting this case:
Nice Problem. For those getting WA consider the case of a single vertex with a self loop.
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...
@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 :)
@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.