0 like 0 dislike
1,589 views

retagged | 1,589 views

0 like 0 dislike
Problem Statement:

You are given a map consisting of N cities. Each city has a directed path to another city or it can be to itself (this means, each city has exactly one outgoing edge).

You are given an array arr. There is a directed path from city i to arr[i] , where 1<=i<=N

You have to start from every city and then travel through cities until you reach a city that you have already visited before.

Task: For each city, determine the number of cities you would visit if you start from that city.

Note: 1-based indexing is followed in the problem.

Example:

Assumptions: N=3
arr=[2,3,1]

Approach:

You have three edges in the graph.
1st edge is from city 1 to city arr[0] that is city 2.
2nd edge is from city 2 to arr[1] that is city 3.
3rd edge is from city 3 to arr[2] that is city 1.
Starting from city1, you visit city 1,2 and 3. There is a path from city 3 to 1, but city 1 is already visited.
Starting from city2, you visit city 2,3 and 1. There is a path from city 1 to 2, but city 2 is already visited.
Starting from city1, you visit city 3,1 and 2. There is a path from city 2 to 3, but city 3 is already visited.
Thus, the answer array is [3,3,3]

Input Format:

First line is T , no of test cases.
For each test case, first line contains a single integer N, no of cities
the second line contains an array arr denoting the array containing the destination city for paths from each city.

Output Format:

For each test case, print N integers acc to problem statement.

Constraints:

1<=T<=100
1<=N<2x10^5
1<=arr[i]<=N for all 1<=i<=N
Sum of all N[i] <2x10^5 for all 1<=i<=T

Sample Input 01:

1
5
2 4 3 1 4

Output:

3 3 1 3 4
by Expert (35,210 points)
0 like 0 dislike

Bny mellon online round

by Expert (35,210 points)