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 \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 0
Sample Output
1 3 2
hide comments
dewa251202:
2018-09-27 05:13:55
I love this |
|
abhimanyu_1998:
2018-09-20 03:48:17
time limit exceeds in java |
|
aman_sachin200:
2018-06-17 22:00:51
Nice one!!!Try CAPCITY and TOUR after this! |
|
sherlock11:
2018-06-08 10:29:56
if u want a clear understanding of SCC then this problem and CAPCITY are the problems that u are looking for.............if u are new with SCC then first read the concepts (kosaraju's algo) and then ......well u know what to do after that.............AC:) |
|
karthik1997:
2017-12-18 09:18:35
Applied Kosaraju's algorithm . Really good problem . :)
|
|
vib_s02:
2017-10-29 09:46:51
@justforpractic
|
|
minaamir26:
2017-08-17 06:52:31
too strict time for java users |
|
asib_133012:
2017-05-25 12:43:02
4 4
|
|
ayush_1997:
2017-03-10 21:17:24
learned the concept of sink vertex :)
|
|
flyingduchman_:
2017-03-03 16:55:41
A correct algorithm : (Not easily available on the internet)
|
Added by: | Wanderley Guimarăes |
Date: | 2007-09-21 |
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 |