SAC '21 P5 - Friends of Friends

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types

After a student started a rumour, you have been tasked with implementing a system to count the number of people that heard it for the N students in the school: you will be asked Q queries of 2 types:

1 u v: u and v are now friends and can spread the rumour from their friends to each other.

2 x: If x started a rumour, output the number of people that heard the rumour, including the starter.

Input Specification

The first line will contain N and Q, the number of students and the number of queries.

The next Q lines will contain one of the above queries.

Output Specification

Output the answer to each type 2 query.


For all subtasks:

1 \leq N, Q \leq 100\,000

1 \leq u, v, x \leq N

Subtask 1 [40%]

1 \leq N, Q \leq 1\,000

Subtask 2 [60%]

No additional constraints.

Sample Input

5 6
2 3
1 1 2
1 2 3
2 1
1 4 5
2 4

Sample Output


Explanation for Sample Output

For the 1^\text{st} query, the 3^\text{rd} student is only able to reach himself, so the answer is 1. For the 2^\text{nd} query, the 1^\text{st} student can reach himself and the 2^\text{nd} and 3^\text{rd} student. For the 3^\text{rd} query, the 4^\text{th} person can only reach himself and the 5^\text{th} student.


  • 1
    kresteodymium  commented on June 9, 2021, 8:33 p.m.

    My DFS TLEd on the 3rd batch :(

    • 6
      vishnus  commented on June 10, 2021, 12:01 p.m.

      DFS will most likely TLE for this problem. Try using another data structure. You can also check the editorial for more tips.