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.
Input
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.
Output
The output file contains an integer denoting the number of candidate cities followed by the list of candidate cities in increasing order.
Example
Input: 4 4 1 2 3 2 4 3 2 1 Output: 2 1 2
hide comments
|
vjvjain0:
2019-05-28 22:55:16
Used (Kosaraju + dfs) WA on 20
|
|
nour_massri:
2019-05-15 22:40:04
Weak Test cases my code is giving WA for this test case but it gives AC when submitted !!
|
|
aditya_305:
2019-05-15 07:21:24
Long implemention !! |
|
great_coder1:
2019-03-29 10:59:16
What do we mean by candidate cities
|
|
az2019:
2019-03-23 09:54:59
B_U_T_ful
|
|
ameernsr:
2019-03-23 08:10:30
badihijat!
|
|
malish_228:
2019-03-04 18:27:38
GG easy scc + dfs |
|
lamia2658:
2019-02-03 07:30:36
the nodes which are involved in an SCC whose size is > 1 is the answer. Dont forget to sort the answer before submitting ;)
|
|
paras meena:
2018-11-25 21:58:36
Time constraint for java is not added properly. Converted same TLE java code in C++ and got AC.
|
|
ashishgup:
2018-09-18 22:44:31
20th test case for me was not printing the cities in increasing order :( |
| Added by: | Narek Saribekyan |
| Date: | 2010-06-20 |
| Time limit: | 1s-4s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |
| Resource: | Armenian TST 2010, Round 2 |
RSS