"You have 1 mutual friend"

Every social app shows this line when you open someone's profile. How does it work? Take your friend list and their friend list, and count the names that appear on both.

To make "is this person on their list?" instant, store each person's friends in a set instead of a list, the same trick you used in Hashing.

Same as before: just sets instead of lists.

Membership check: a one-step question, no scanning.

In code

adj = [set() for _ in range(n)]
for u, v in edges:
    adj[u].add(v)
    adj[v].add(u)
return len(adj[a] & adj[b])

Friends [[0, 1], [0, 2], [1, 2], [2, 3], [3, 4]] · a = 0, b = 3

adj[0]: {1, 2}
mutual: 0

Start with a = 0. Its friends are 1 and 2.

Move 1 of 5

Walk one list, check the other

Go through the first person's friends one by one. For each friend, ask the second person's set "do you have this person too?" and count the yeses. You only walk one list, so the work is about the size of one friend list, not the whole network.

Try it below with person 0 and person 3.

Friends in both lists: that is the mutual-friend count.

The two people themselves: if they are friends, neither counts as a mutual friend.