Build the follower graph

Scenario

A social app stores every follow as a pair of account numbers: [a, b] means account a follows account b. The accounts are numbered 0 to n - 1.

You work on the profile page. To show "Following", the page needs, for each account, the list of accounts it follows, sorted by number. The raw list of pairs is long and in no useful order.

Your task

Write build_following(n, follows).

n is the number of accounts.
follows[i] = [a, b] means account a follows account b. The same pair can appear more than once, and nobody follows themselves.
Return a list of n lists. The list at position i holds every account that account i follows, from the smallest number to the largest, with no repeats. An account that follows nobody gets an empty list.

Examples

Example 1 (traced)#

text2 lines

Input:  n = 4, follows = [[0, 1], [0, 2], [2, 1], [3, 0], [0, 1]]
Output: [[1, 2], [], [1], [0]]

Account	Pairs that start at it	Its list
0	`[0, 1]`, `[0, 2]`, `[0, 1]`	1, 2 (the repeat is dropped)
1	none	empty
2	`[2, 1]`	1
3	`[3, 0]`	0

Account 1 follows nobody, so its list is empty.

Example 2#

text2 lines

Input:  n = 3, follows = []
Output: [[], [], []]

There are no pairs, so every list is empty. Each account still has a row.

Example 3#

text2 lines

Input:  n = 2, follows = [[1, 0]]
Output: [[], [0]]

A follow goes one way. Account 1 follows account 0, but account 0 follows nobody.

Constraints

1 ≤ n ≤ 10^5
0 ≤ length of follows ≤ 10^5
0 ≤ a, b < n for every pair, and a ≠ b

What does n ≤ 10^5 tell you?

There can be 100,000 accounts and 100,000 pairs. Scanning every pair once for each account would be 100,000 times 100,000 steps, about ten billion. That is far too slow.

You want to read each pair once and put it in the right list straight away. A list of lists, one for each account, does that. The sorting at the end costs a little more, but it is far below the limit.

Scenario

A social app stores every follow as a pair of account numbers: [a, b] means account a follows account b. The accounts are numbered 0 to n - 1.

You work on the profile page. To show "Following", the page needs, for each account, the list of accounts it follows, sorted by number. The raw list of pairs is long and in no useful order.

Your task

Write build_following(n, follows).

n is the number of accounts.
follows[i] = [a, b] means account a follows account b. The same pair can appear more than once, and nobody follows themselves.
Return a list of n lists. The list at position i holds every account that account i follows, from the smallest number to the largest, with no repeats. An account that follows nobody gets an empty list.

Examples

Example 1 (traced)#

text2 lines

Input:  n = 4, follows = [[0, 1], [0, 2], [2, 1], [3, 0], [0, 1]]
Output: [[1, 2], [], [1], [0]]

Account	Pairs that start at it	Its list
0	`[0, 1]`, `[0, 2]`, `[0, 1]`	1, 2 (the repeat is dropped)
1	none	empty
2	`[2, 1]`	1
3	`[3, 0]`	0

Account 1 follows nobody, so its list is empty.

Example 2#

text2 lines

Input:  n = 3, follows = []
Output: [[], [], []]

There are no pairs, so every list is empty. Each account still has a row.

Example 3#

text2 lines

Input:  n = 2, follows = [[1, 0]]
Output: [[], [0]]

A follow goes one way. Account 1 follows account 0, but account 0 follows nobody.

Constraints

1 ≤ n ≤ 10^5
0 ≤ length of follows ≤ 10^5
0 ≤ a, b < n for every pair, and a ≠ b

What does n ≤ 10^5 tell you?

There can be 100,000 accounts and 100,000 pairs. Scanning every pair once for each account would be 100,000 times 100,000 steps, about ten billion. That is far too slow.