618 · Search Graph Nodes [LintCode]

2649 mstime cost

·

22.94 MBmemory cost

·

Your submission beats11.00 %Submissions

 /**

* 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) {

// write your code here

Queue<UndirectedGraphNode> que = new ArrayDeque<>();

Set<UndirectedGraphNode> visited = new HashSet<>();

que.offer(node);

visited.add(node);

if (values.containsKey(node) && values.get(node) == target) {

return node;

}

while (!que.isEmpty()) {

UndirectedGraphNode curr = que.poll();

for (UndirectedGraphNode next : curr.neighbors) {

if (visited.contains(next)) {

continue;

}

if (values.containsKey(next) && values.get(next) == target) {

return next;

}

visited.add(next);

que.offer(next);

}

}

return null;

}

}