Advertisement
Guest User

Untitled

a guest
Jan 22nd, 2019
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.51 KB | None | 0 0
  1.     // Complete the bfs function below.
  2.    static int[] bfs(int n, int m, int[][] edges, int s) {
  3.      
  4.       Queue<Integer> q = new LinkedList();
  5.         HashMap<Integer, Integer> visited = new HashMap();
  6.         HashMap<Integer, Integer> results = new HashMap();
  7.        int[] finalResults = new int[n-1];
  8.        int[] levels = new int[n + 1];
  9.         q.add(s);
  10.        levels[s]= 0;
  11.       // System.out.println("n = " + n );
  12.      
  13.         for(int i = 1; i <= n; i++){
  14.             if(s!=i)
  15.             results.put(i, -1);
  16.         }
  17.         for (Map.Entry<Integer, Integer> entry : results.entrySet()) {
  18.     //   System.out.println(entry.getKey() + " : " + entry.getValue());
  19.            //   finalResults[count++] = entry.getValue();
  20.        
  21.  
  22.     // ...
  23. }
  24.         while(!q.isEmpty()) {
  25.          
  26.             int current = q.remove();
  27.            // visited.add(current);
  28.             // HashMap<Integer, Integer> list = new HashMap();
  29.             Queue<Integer> list = new LinkedList();
  30.             for(int i = 0; i < edges.length; i++) {
  31.                if(edges[i][0] == current)
  32.                    list.add(edges[i][1]);
  33.                // System.out.println("list["+i+"]" + " =" +list[i]);
  34.             }
  35.          
  36.            
  37.              //System.out.println("current" + " =" +current);
  38.             int i = 0;
  39.             while(!list.isEmpty()){
  40.                
  41.          
  42.                 if(!visited.containsValue(list.peek())) {
  43.                     int c = list.remove();
  44.                         levels[c] = levels[current] + 1;
  45.                    // System.out.println("list " + list[i]);
  46.                         if(levels[c] != 0){
  47.                            
  48.                         results.put(c,(6*levels[c]));
  49.                            
  50.                         }else{
  51.                              results.put(c,6);
  52.                         }
  53.                     visited.put(i++,c);
  54.                         q.add(c);
  55.                 }
  56.            
  57.            
  58.  
  59.         }
  60.        int count = 0;
  61.       for (Map.Entry<Integer, Integer> entry : results.entrySet()) {
  62.     //   System.out.println(entry.getKey() + " : " + entry.getValue());
  63.               finalResults[count++] = entry.getValue();
  64.        
  65.  
  66.     // ...
  67. }
  68.      
  69.          
  70.        
  71.         // for(int i = 0; i<= n; i++ ) {
  72.         //     if(!results.containsKey(i)) finalResults[i - s - 1] = -1;
  73.         //     else finalResults[i - s - 1] = results.get(i);
  74.         // }
  75.         }
  76.         return finalResults;
  77.  
  78.    
  79.    }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement