SAC '21 Code Challenge P5 - Friends of Friends

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

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$ $N$ students in the school: you will be asked $Q$ $Q$ queries of $2$ $2$ types:

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

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

Input Specification

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

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

Output Specification

Output the answer to each type $2$ $2$ query.

Constraints

For all subtasks:

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

$1 \le u, v, x \le N$ $1 \leq u, v, x \leq N$

Subtask 1 [40%]

$1 \le N, Q \le 1\,000$ $1 \leq N, Q \leq 1 000$

Subtask 2 [60%]

No additional constraints.

Sample Input

Copy

Sample Output

Copy

1
3
2

Explanation for Sample Output

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

Comments

1

kresteodymium commented on June 10, 2021, 12:33 a.m. ← edited →

My DFS TLEd on the 3rd batch :(

6

vishnus commented on June 10, 2021, 4:01 p.m. ← edited →

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