[LintCode] Six Degrees

时间：2017-11-11 10:26:28 阅读：200 评论：0 收藏：0 [点我收藏+]

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

 1 /**
 2  * Definition for Undirected graph.
 3  * class UndirectedGraphNode {
 4  *     int label;
 5  *     List<UndirectedGraphNode> neighbors;
 6  *     UndirectedGraphNode(int x) { 
 7  *         label = x;
 8  *         neighbors = new ArrayList<UndirectedGraphNode>(); 
 9  *     }
10  * };
11  */
12 
13 
14 public class Solution {
15     public int sixDegrees(List<UndirectedGraphNode> graph, UndirectedGraphNode s, UndirectedGraphNode t) {
16         if(graph == null || !graph.contains(s) || !graph.contains(t)) {
17             return -1;
18         }
19         if(s == t) {
20             return 0;
21         }
22         Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>();
23         Set<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>();
24         int layer = 1;
25         q.add(s);
26         visited.add(s);
27         while(!q.isEmpty()) {
28             int size = q.size();
29             for(int i = 0; i < size; i++) {
30                  UndirectedGraphNode curr = q.poll();
31                  for(UndirectedGraphNode neighbor : curr.neighbors) {
32                      if(visited.contains(neighbor)) {
33                          continue;
34                      }
35                      if(neighbor == t) {
36                         return layer; 
37                      }
38                      else {
39                          q.add(neighbor);
40                          visited.add(neighbor);
41                      }
42                  }
43             }
44             layer++;
45         }
46         return -1;
47     }
48 }