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
kshubham02: 2016-06-12 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.
In TC1, from 1 you can reach only 3 and from 3 you can reach 1. Hence 1 is a sink.
From 2 you can reach 3 but from 3 you cannot reach 2. Hence 2 is not a sink.
From 3 you can reach only 1 and from 1 you can reach back to 3. Hence 3 is also a sink.

Abhishek Naik: 2016-04-22 15:31:43

I didn't understand the 2nd test case. There is an edge from 1->2 and implicitly from 2->2. Going by this implication, in the first test case, we should also have had 1->1, 2->2 and 3->3, in addition to 1->3 and 3->1. Could someone please explain this to me?

[Mayank Pratap]: 2016-04-10 11:15:39

My first SCC Problem :)

shivam_uttra: 2016-04-05 20:41:14

can someone suggest me tricky test case..i'm constantly getting wa ....all the test cases in the problems and comments are passing :(

Reem Obaid: 2016-03-19 20:35:12

Try this:
3 3
1 2 2 1 2 3

GAURAV CHANDEL: 2016-02-23 15:41:36

Yes..We All Are Strongly Connected...

varun yadav: 2016-01-25 11:19:37

cake walk :) simple scc problem

Deepak : 2016-01-24 18:48:57

nice one..AC in one go..

kejriwal: 2015-12-16 19:46:20

nice one !!

Saumye Malhotra: 2015-10-24 10:35:27

What is to be done when a graph has multiple bottoms?do we have to print the nodes of bottom with maximum size? If yes, in second case there are two bottoms both of size 1, why is only 2 printed.
Someone please help.
Thanks in advance.

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