WAP Interview Question
Country: United States
bfs find shortest path between two nodes
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner (System.in);
int n = sc.nextInt() ;
int m = sc.nextInt() ;
int i = 0 ;
int [][] data = new int [n - 1][2] ;
while (i < n - 1) {
data[i][0] = sc.nextInt() ;
data[i][1] = sc.nextInt() ;
i++;
}
i = 0 ;
int [][] query = new int [m][2] ;
while (i < m) {
query[i][0] = sc.nextInt() ;
query[i][1] = sc.nextInt() ;
i++;
}
getPath(data, query, n);
}
public static HashMap<Integer,List<Integer>> createGraph (int n, int [][] ar){
HashMap<Integer,List<Integer>> graph = new HashMap<> ();
for (int i = 1 ; i <= n ; ++i) {
graph.put(i, new ArrayList<Integer>());
}
for (int [] a : ar) {
graph.get(a[0]).add(a[1]) ;
graph.get(a[1]).add(a[0]) ;
}
return graph ;
}
public static void getPath (int [][] ar, int [][] query,int n){
HashMap<Integer,List<Integer>> graph = createGraph (n ,ar);
HashMap<Integer,Boolean> city = new HashMap<> ();
city.put(1, true) ;
for (int [] a : query) {
if (a[0] == 1) {
city.put(a[1], true) ;
} else {
bfs (graph,city, a[1]);
}
}
}
public static void bfs (HashMap<Integer,List<Integer>> graph, HashMap<Integer,Boolean> city , int start){
HashMap<Integer,Integer> visited = new HashMap<> ();
Queue<Integer> q = new LinkedList<> () ;
visited.put(start, 0) ;
q.offer(start) ;
while (!q.isEmpty()) {
int cur = q.poll() ;
if (city.containsKey(cur)) {
System.out.println(visited.get(cur));
break;
}
for (int n : graph.get(cur)) {
if (!visited.containsKey(n)) {
visited.put(n, visited.get(cur) + 1) ;
q.add(n) ;
}
}
}
}
Segment tree could be one possible solution but don't know how to change this problem in Segment tree, any suggestions?
- topCoder September 28, 2015