I’ve been stuck with this problem for a few weeks or so, but I couldn’t think of the full solution yet. I would appreciate it if you could give me any ideas. Thank you in advance!
The problem says.
You are given a graph consisting of N vertices labeled from 1 to N and M directed edges. The graph may be disconnected. You need to travel between vertices with a specific rule. The rule is:
To travel from vertex u to vertex v (where u != v ), you must follow a sequence of vertices ( p_0 = u, p_k = v ) such that the movement alternates between “up” and “down”:
• If p_i < p_{i+1} , then p_{i+1} > p_{i+2} .
• If p_i > p_{i+1} , then p_{i+1} < p_{i+2} .
You are asked several queries. For each query, starting from a given vertex, you must determine how many other vertices you can reach under the given travel rules.
Input:
• The first line contains three integers N , M , and Q representing the number of vertices, edges, and queries, respectively. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 200,000, 1 ≤ Q ≤ N ).
• The next M lines each contain two integers u_i and v_i (1 ≤ u_i, v_i ≤ N ) representing a directed edge from vertex u_i to vertex v_i .
• The next Q lines each contain an integer c_i (1 ≤ c_i ≤ N ) representing the starting vertex for each query.
Output:
For each query, output the number of vertices that can be reached from the starting vertex under the given rules.
Test Cases:
The problem is divided into four test cases:
1. Test Case 1 (20 points): M = N - 1 , and the edges connect consecutive vertices (i.e., u_i = i and v_i = i + 1 ). It is guaranteed that every vertices can be reached from any other building.
2. Test Case 2 (20 points): M = N - 1 , and each vertices has at most 2 connecting edges. It is guaranteed that every vertices can be reached from any other vertices.
3. Test Case 3 (40 points): N does not exceed 200.
4. Test Case 4 (20 points): No additional constraints.
Example Input:
5 4 3
1 2
2 3
3 4
3 5
1
2
3
Example Output:
1
2
3
It’s my first time writing blog here, sorry if it’s not clear to you.
