Hii!!! I took part in the Atcoder ACL contest 1 held a few days ago. Unfortunately, I am getting wrong answer in the first problem Reachable towns, here is my submission.

All I have done is to sort all cities according to x keeping their city numbers, and connect each city to next city with greater y and x coordinate than it with a bidirectional edge, and finally answer will be the size of connected component of graph for every city. Please tell me if I am incorrect somewhere.

Thanks in advance!!

I guess because the relation is not transitive. Take three cities at (4, 6),(6, 8),(5, 3). Then {(4,6),(6,8)} ∈ R, {(6,8),(5,3)} ∈ R, but {(4,6),(5,3)}∉R

Even in this example, any city is reachable from the other.

Let city 1 be at (4,6), 2 at (6,8), 3 at (5,3). Then you can reach city 2 from city 1 and city 3 from city 2, hence you can reach city 3 from city 1 too.

This is shown in the sample test case 2 of the problem, where number of cities reachable from city 2 is 3. But point to be noted, the only directly reachable city is city 1, and since city 1 is connected to two extra cities, 2 more cities become reachable from city 2.

In other words, indirectly reachable cities are to be counted.

Hmm what does your program get for this case:

https://www.imageupload.net/image/E6Vh2

If you're only connecting a point with the next one with greater y, then the edge between A and B will be drawn, but I think you'll miss the edge from A to C.

EDIT: Yup, that is the issue. On this test case:

Your output: 2 2 1

Answer: 3 3 3

Thanks!! I got it :).

In the first question, I have used this approach, but it is giving

`TLE`

, can anyone help me? How can I improve this approach and what modifications should I do here?