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։ 1N≤100,000 and 1M≤200,000. Each of the following M lines contains two integers 1A, 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
aman_sachin200: 2018-06-17 21:06:13

Awesome One!!!!Don't forget to print the cities in increasing order!!!!Similar problem TOUR !!:P

ankitraj7217: 2018-06-06 08:33:21

Weak test cases..No test cases for 0 capital city..

Last edit: 2018-06-06 08:41:55
dipankar12: 2018-05-20 13:51:03

Last edit: 2018-05-20 13:51:55
mohit_aggarwal: 2018-03-01 09:18:26

AC in one Go :-p
Nice Problem !!

johnwalkerwa: 2018-02-18 07:50:14

Honestly, is this solvable with java? Maybe I'm just bad.

ramini1996: 2018-02-09 15:00:04

My 20th test case is accepted when I ran my DFS on reverse graph starting from every single node which is not explored.There is no case where the graph contains components that are not at all connected to each other. So, there is at least one capital city always.

Last edit: 2018-02-09 15:01:00
shubh619: 2018-01-29 14:22:38

Getting WA on TEST CASE 20.Can Anyone Tell why and what it could be?

peregrine: 2017-12-30 20:29:02

My 2nd submission was a wrong code, but got AC

botanich: 2017-09-14 17:28:10

@scorpion_ajay pls tell me where writen about its no cases without any capital city? I cant find it

Last edit: 2017-09-14 17:45:15
pratham_1: 2017-09-11 21:53:57

Bad time limit for java ;(

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