Six Degrees

题目：

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.

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

分析：

微软的考试题，用标准bfs可以解。但是注意在bfs的过程中，需要多一重for循环来记录层数，或者degree数。

解法：

class Solution {
public:
    /**
     * @param graph a list of Undirected graph node
     * @param s, t two Undirected graph nodes
     * @return an integer
     */
    int sixDegrees(vector<UndirectedGraphNode*> graph,
                   UndirectedGraphNode* s,
                   UndirectedGraphNode* t) {
        // Write your code here
        if (s == t) {
            return 0;
        }
        unordered_set<UndirectedGraphNode* > visited;
        queue<UndirectedGraphNode* > Q;
        Q.push(s);
        visited.insert(s);
        int count = 1;
        while (!Q.empty() ) {
            int size = Q.size();
            for (int i = 0; i < size; i++) {
                UndirectedGraphNode* temp = Q.front();
                Q.pop();
                for (int j = 0; j < temp->neighbors.size(); j++) {
                    if (temp->neighbors[j] == t) {
                        return count;
                    }
                    if (visited.find(temp->neighbors[j]) == visited.end() ) {
                        visited.insert(temp->neighbors[j]);
                        Q.push(temp->neighbors[j]);
                    }
                }
            }
            count++;
        }
        return -1;
    }
};