Six degrees of separation is the theory that everyone and everything is six or fewer steps away, by way of introduction, from any other person in the world, so that a chain of "a friend of a friend" statements can be made to connect any two people in a maximum of six steps.

Given a friendship relations, find the degrees of two people, return-1if they can not been connected by friends of friends.

Have you met this question in a real interview?

Yes

Example

Gien a graph:

1------2-----4
 \          /
  \        /
   \--3--/

{1,2,3#2,1,4#3,1,4#4,2,3}and s =1, t =4return2

Gien a graph:

1      2-----4
             /
           /
          3

{1#2,4#3,4#4,2,3}and s =1, t =4return-1

1. bfs to the point, 1 degree is 1 level

/**
 * Definition for Undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { 
 *         label = x;
 *         neighbors = new ArrayList<UndirectedGraphNode>(); 
 *     }
 * };
 */
public class Solution {
    /**
     * @param graph a list of Undirected graph node
     * @param s, t two Undirected graph nodes
     * @return an integer
     */
    public int sixDegrees(List<UndirectedGraphNode> graph,
                          UndirectedGraphNode s,
                          UndirectedGraphNode t) {
        // Write your code here
        if (graph == null || graph.size() == 0) {
            return -1;
        }

        if (s.label == t.label) {
            return 0;
        }

        Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
        HashSet<UndirectedGraphNode> isVisited = new HashSet<UndirectedGraphNode>();

        queue.offer(s);
        int degree = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            degree++;
            for (int i = 0; i < size; i++) {
                UndirectedGraphNode cur = queue.poll();
                for (UndirectedGraphNode neighbor : cur.neighbors) {
                    if (neighbor.label == t.label) {
                        return degree;
                    }

                    if (isVisited.contains(neighbor)) {
                        continue;
                    }

                    queue.offer(neighbor);
                    isVisited.add(neighbor);
                }
            }
        }

        return -1;

    }
}