| Submit | All submissions | Best solutions | Back to list |
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
| 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 |
hide comments
|
||||||||||||
|
2024-08-08 23:35:17
poor test case, there is only one ssc, and we have to print that only, in increasing order |
||||||||||||
|
2023-10-23 18:00:16
dont forget: you should print candidate cities in increasing order. |
||||||||||||
|
2023-03-31 22:09:01
In question there should be given that at least one city is reachable from all other cities, or they need to change the test cases, include test cases where answer is 0. |
||||||||||||
|
2022-06-21 21:15:41
There are missing test cases for this problem 8 9 1 2 2 3 3 4 4 5 5 2 1 6 6 7 7 8 8 6 test like this , there are two SCC and they can't reach each other, I have submitted a solution its result is the nodes on the two SCC and this doesn't seem right because the answer should be 0 here's the code that gets wrong result <snip> [Simes]: Please use the forum for this. Last edit: 2022-06-22 21:39:23 |
||||||||||||
|
2021-09-30 08:52:45
4 3 4 1 1 1 3 2 1 2 2 2 3 2 4 3 2 3 3 8 5 11 1 3 1 5 2 2 2 3 2 5 2 8 3 4 3 5 3 6 3 7 4 3 4 6 5 1 5 6 6 1 6 2 6 4 6 5 7 2 7 5 7 7 7 8 Output #1 3 #2 2 Last edit: 2022-06-22 08:06:26 |
||||||||||||
|
2021-07-10 13:19:58
nice problem |
||||||||||||
|
2021-05-17 15:24:30
Same as TOUR only difference is find outdegree instead of indegree in this problem..!! SCC :) |
||||||||||||
|
2021-02-26 18:41:17
A nice problem |
||||||||||||
|
2021-01-14 19:09:08
dont forget: you should print candidate cities in increasing order. |
||||||||||||
|
2020-05-14 21:40:27
Poor test Cases Framed Wont work where there is not a single candidate City For eg: test case: 8 6 1 2 2 3 3 4 5 4 6 7 8 7 : It'a answer should be 0 |
||||||||||||
RSS