Lintcode 618. Search Graph Nodes

Given a undirected graph, a node and a target, return the nearest node to given node which value of it is target, return NULL if you can't find.

There is a mapping store the nodes' values in the given parameters.

Example

Example 1:

Input:
{1,2,3,4#2,1,3#3,1#4,1,5#5,4}
[3,4,5,50,50]
1
50
Output:
4
Explanation:
2------3  5
 \     |  | 
  \    |  |
   \   |  |
    \  |  |
      1 --4
Give a node 1, target is 50

there a hash named values which is [3,4,10,50,50], represent:
Value of node 1 is 3
Value of node 2 is 4
Value of node 3 is 10
Value of node 4 is 50
Value of node 5 is 50

Return node 4

Example 2:

Input:
{1,2#2,1}
[0,1]
1
1
Output:
2

Notice

It's guaranteed there is only one available solution

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

/**  * Definition for graph node.  * class UndirectedGraphNode {  *     int label;  *     ArrayList<UndirectedGraphNode> neighbors;  *     UndirectedGraphNode(int x) {  *         label = x; neighbors = new ArrayList<UndirectedGraphNode>();  *     }  * };  */     public class Solution {     /*      * @param graph: a list of Undirected graph node      * @param values: a hash mapping, <UndirectedGraphNode, (int)value>      * @param node: an Undirected graph node      * @param target: An integer      * @return: a node      */     public UndirectedGraphNode searchNode(ArrayList<UndirectedGraphNode> graph,                                           Map<UndirectedGraphNode, Integer> values,                                           UndirectedGraphNode node,                                           int target) {         // BFS         //         Queue<UndirectedGraphNode> queue = new LinkedList<>();         Set<UndirectedGraphNode> visited = new HashSet<>();           // pre-process the graph         //         Map<UndirectedGraphNode, List<UndirectedGraphNode>> adjList  = new HashMap<>();         for (UndirectedGraphNode e : graph) {             adjList.put(e, e.neighbors);         }           queue.offer(node);         visited.add(node);           while (!queue.isEmpty()) {             UndirectedGraphNode curNode = queue.poll();             if (values.get(curNode) == target) {                 return curNode;             }               for (UndirectedGraphNode neighbor : adjList.get(curNode)) {                 if (!visited.contains(neighbor)) {                     queue.offer(neighbor);                     visited.add(neighbor);                 }             }         }           return null;     } }