CAPCITY - Capital City

There are N cities in Flatland connected with M unidirectional roads. The cities are numbered from 1 to N. The Flat Circle of Flatland (FCF) wants to set up a new capital city for his kingdom. For security reasons, the capital must be reachable from all other cities of Flatland. FCF needs the list of all candidate cities. You are the chief programmer at FACM (Flat Association for Computing Machinery) responsible for providing the list to FCF as soon as possible.


The first line of the input file contains two integers: 1 ≤ N ≤ 100,000 and 1 ≤ M ≤ 200,000. Each of the following M lines contains two integers 1 ≤ A, B ≤ N denoting a road from A to B.


The output file contains an integer denoting the number of candidate cities followed by the list of candidate cities in increasing order.


4 4
1 2
3 2
4 3
2 1

1 2

hide comments
Archit Jain: 2014-12-03 16:41:40

nice one!

Sumit: 2014-12-02 22:18:16

Guys take care about the increasing order condition cost me 5 wa's

vishal: 2014-11-30 07:04:30

wa on 20th test case..!!

Ankur Singh: 2014-11-11 12:08:48

nice problem ... taught me kernel DAG

Ayush Vatsa: 2014-10-31 07:16:01

very weak test cases.....wrong algorithm is getting accepted

mohsin mohammad: 2014-08-15 21:25:29

Easy graph problem....

Adarsh Mohata: 2014-06-15 10:59:42

Exactly same problem as TOUR..just need to change the constraints.Also,the test cases are very weak compared to TOUR

Last edit: 2014-06-15 11:00:33
Pratik kumar: 2014-02-04 19:29:55

weak test cases :(

cegprakash: 2014-01-06 12:18:32

There is no test case in which there is no capital city. Add it plz..

Last edit: 2016-07-29 22:20:13
npsabari: 2014-01-14 08:14:39

Simple one, given you know about the maximal connected subgraphs!

Added by:Narek Saribekyan
Time limit:1s-4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:Armenian TST 2010, Round 2