Degrees of Separation

A social app has n users numbered 0 to n - 1, and edges lists mutual friendships [a, b].

For a given user source, return an array dist of length n where dist[i] is the smallest number of friendship links between source and user i, or -1 if user i cannot be reached. dist[source] is 0.

Example 1

Input:: n = 6, edges = [[0,1],[0,2],[1,3],[2,3],[3,4]], source = 0
Output:: [0,1,1,2,3,-1]

User 3 is a friend of a friend; user 4 is one step further; user 5 has no friends.

Example 2

Input:: n = 3, edges = [[1,2]], source = 2
Output:: [-1,1,0]

Constraints

1 ≤ n ≤ 10^5
0 ≤ edges.length ≤ 2 · 10^5
0 ≤ a, b, source < n

Hint

Show the first hint

All links have the same length. Which traversal visits nodes in order of distance?

Walkthrough

How to approach it

01Clarify before coding

Are friendships symmetric? Yes, the graph is undirected.
What should unreachable users get? -1.
Is the distance counted in links (edges)? Yes.

02Brute force

For each user i, run a separate search from source until it finds i.

Cost: n searches of O(V + E) each: O(V · (V + E)), around 3 · 10^10 at the limits.

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 browser Start free

This problem is part of Pro.