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

Hey @asib_133012
The scc's are [3] , [4] and [1,2] . Since 3-4 edge exists , you cannot take 3 as sink . All other scc's have nodes that are actually sinks .
So the bottoms are 1,2,4 -> output :)

Last edit: 2017-12-18 09:19:28
vib_s02: 2017-10-29 09:46:51

@justforpractic

I think that answer should be 1 2

minaamir26: 2017-08-17 06:52:31

too strict time for java users

asib_133012: 2017-05-25 12:43:02

4 4
1 2 2 1 3 2 3 4
0
In this case what should be the ans? and why? please explain someone.thanks in advance

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)

Theorem : A strongly connected component (all vertices) is sink(i.e. all vertices are sink) if every vertex in a scc is connected to no other scc than itself's.

Find all strongly connected component(scc)s by Kosaraju or Tarjan's algorithm and store them. Now, for every vertex in a scc, if you find an adjacent vertex (in the adjacency list) let's call it "v" such that v is not in that scc, then discard the whole scc. That is, when a vertex of a scc(No.1) is adjacent to a different scc(No.2) then discard scc(No.1), otherwise take all vertices of scc(No.1) to the "result" array or container. Do this for all scc s. After that, sort the "result" array and print it.

Last edit: 2017-03-03 17:01:37

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