Advertisement
wgma

Untitled

Sep 25th, 2016
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.01 KB | None | 0 0
  1.     // The task is to use breadth-first search to find out how many disjoint graphs there are
  2.     static int friendCircles(String[] friends) {
  3.         int[] visited = new int[friends.length]; // people we have checked
  4.         int disjoint_graphs = 0;
  5.         for (int start_node = 0; start_node < friends.length; start_noe++) {
  6.             if(!visited[start_node]){
  7.                 LinkedList<Integer> queue = new LinkedList<>();
  8.                 queue.add(start_node);
  9.                 while(!queue.empty()){
  10.                     Integer current_node = queue.remove();
  11.                     for(int next_node = 0; next_node < friends[current_node].length();next_node++){
  12.                         if(!visisted[next_node] && friends[current_node].charAt(next_node) == 'Y'){
  13.                             queue.add(next)node);
  14.                             visited[next_node] = true;
  15.                         }
  16.                     }
  17.                 }
  18.                 disjoint_graphs++;
  19.             }
  20.         }
  21.         return disjoint_graphs;
  22.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement