Cluster Size of Each Node

EasyGraphs

Problem

A social app has n users numbered 0 to n - 1. Each entry [a, b] of friendships is a mutual friendship.

For every user, report how many users are in their friend cluster (the users reachable through chains of friendships, including themselves). Return an array sizes where sizes[i] is that number for user i.

Example 1

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

Example 2

Input:
n = 3, friendships = []
Output:
[1, 1, 1]

Example 3

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

Constraints

  • 1 ≤ n ≤ 10^5
  • 0 ≤ friendships.length ≤ 2·10^5
  • 0 ≤ a, b < n

Hint

Show the first hint

If you knew which cluster each user belongs to, how would you get its size?

Walkthrough

How to approach it

01Clarify before coding

  • Does a user count themselves? Yes, a user with no friends has size 1.
  • Are friendships mutual? Yes, undirected.
  • Can a friendship repeat or link a user to themselves? Yes; it must not inflate the size.

02Brute force

Run a BFS from every user and count how many users it reaches.

Cost: O(n · (n + m)): 3·10^10 steps for a single giant cluster.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.