CareerCup

This is can also be done using two BFS searches - one from person A and one from person B.

BFS algorithm explores every node at a distance/radius k from the source node before it moves to distance k+1.  The algorithm also keeps a track of visited nodes by coloring them as white(not explored), gray(being explored) and black(explored).

Run two BFS searches from A and B:-
1.  From A, let the explored radius be X, let the colors used for exploration be g1 and b1
2.  From B, let the explored radius be Y, let the colors used for exploration be g2 and b2

Explore all nodes from A with X = 1, then from B with Y = 1, then from A with X = 2.. and so on.

During exploration whenever BFS from A encounters a node colored b2 or vice versa, the search can be terminated.

The degree of separation is X + Y.

You can try this:
1) Create a graph between two people and their friends. If two people know each other (they are present in contacts list) make a vertex.
2) Find the shortest path between person A and B. Number of nodes in the path is the separation degree.

1.first, we should make sure that A,B can be connected, that means there must be at least one path from A to B. we can use Union Find to check it(is root(A)==root(B)?).
2.second, if A,B are conntected, then use BFS to find the shortest path.

What the degree of separation means? it is a distance on the graph?