Free Graphs lessonsGraphs · Stage 2 · Breadth-first · Step 3

Stop after k rings

Count who is within a few hops of you by letting the ripple spread only as far as you ask. About 13 minutes.

How far do you want to see?

Think of a social network. "Friends" are one hop away, "friends of friends" are two hops. A site that suggests people you may know only cares about the first two rings. It would be silly to search the whole network for that.

So give the search a limit. A place at the limit still counts and is still marked, but you skip looking at its neighbours. The ripple stops growing there, and everything outside it is never touched.

Count it, don't expand it: that is what happens at the limit.

Mark on joining: so no place is counted twice.

In code

dist = [-1] * n
dist[start] = 0
queue = deque([start])
while queue:
    node = queue.popleft()
    if dist[node] == k:
        continue
    for nxt in adj[node]:
        if dist[nxt] == -1:
            dist[nxt] = dist[node] + 1
            queue.append(nxt)
return sum(1 for d in dist if d >= 0)

Who is within 2 hops of 0? Rings are shown by distance.

within: 1

Start at 0, distance 0. We want every place within 2 hops. So far that is 1 place.

Move 1 of 4

Ring by ring

Because the queue holds one ring at a time, you can also walk it a whole ring at once. Look at how many places are in the line right now, handle exactly that many, and then you know one full ring is done.

That gives you a natural way to count rings without storing a distance for every place. It is the same search. It is just organised so that "how many rings so far?" is a number you can read off at any moment.

One ring: is the places in the line when the ring began.

Quick check

With a limit of k, the search takes a place at distance exactly k from the line. What should it do with that place's neighbours?

ASkip them, because they would be farther than k
BAdd them to the line like any others
CCount them but don't add them to the line

Show the answer

Skip them, because they would be farther than k. The place itself is counted, but its unseen neighbours are one hop beyond the limit.

Your problem

Within k hops

There are n people, numbered 0 to n − 1. friends[i] = [a, b] means person a and person b are friends (two-way). Return how many people are within k friendships of person start. Person start counts, being 0 friendships from themselves.

Example

n = 8, friends = [[0, 1], [0, 2], [1, 3], [2, 4], [2, 5], [3, 6], [5, 7]], start = 0, k = 2 → 6

1 ≤ n ≤ 100,000 · 0 ≤ friendships ≤ 200,000 · 0 ≤ k ≤ n

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.