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 -1 if they can not been connected by friends of friends.

Example
Gien a graph:

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

Gien a graph:

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

這道題的degreeFromSource不僅用來記錄節(jié)點到source的距離，同時也可以用來記錄是否訪問。因為無向圖里計算某個節(jié)點到source的距離只需要訪問一次圣蝎，不能重復(fù)計算稠曼。

/**
 * 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 || s == t || graph.size() == 0){
            return 0;
        }
        Map<UndirectedGraphNode, Integer> degreeFromSource = new HashMap<>();
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        degreeFromSource.put(s,0);
        queue.offer(s);
        while (!queue.isEmpty()){
            UndirectedGraphNode curt = queue.poll();
            for (UndirectedGraphNode nei : curt.neighbors){
                if (degreeFromSource.containsKey(nei)){
                    continue;
                }
                degreeFromSource.put(nei, degreeFromSource.get(curt) + 1);
                if (nei == t){
                    return degreeFromSource.get(curt) + 1;
                }
                queue.offer(nei);
            }
        }
        return -1;
    }
}