Reading order - MarisaOJ: Marisa Online Judge

HOME
PROBLEMSET
ROADMAP
COMPETITION
TOPIC
RANKING
GUIDE
MASHUP
ABOUT
CONTACT

Marisa got

$n$ strage books from Kourindou, and she wants to read them all. Rinnosuke told her

$m$ constraints of the form

$i, j$ that book

$i$ should be read before book

$j$ . Find an order of reading books, which does not violate any given constraints, for Marisa. ### Input - The first line contains two integers

$n,m$ . - The next

$m$ lines, each line contains two integers

$i, j$ , a constraint. ### Output - Print

$n$ distinct integers, the reading order. Rinnosuke guarantees that the answer exists. If there are more than one answer, print any. ### Constraints -

$1 \le n \le 10^5$ . -

$1 \le i,j \le n$ . ### Example Input:

$5 4 1 2 2 3 1 3 1 5$

Output:

$1 4 2 5 3$

DAG / Topological sort
	DAG
	Reading order
	Longest path
	Maximum path
	Martian language
	Edge direction
	Train pass

Topic

Graph

Rating

1300

Solution (0)

Solution