Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // The task is to use breadth-first search to find out how many disjoint graphs there are
- static int friendCircles(String[] friends) {
- int[] visited = new int[friends.length]; // people we have checked
- int disjoint_graphs = 0;
- for (int start_node = 0; start_node < friends.length; start_noe++) {
- if(!visited[start_node]){
- LinkedList<Integer> queue = new LinkedList<>();
- queue.add(start_node);
- while(!queue.empty()){
- Integer current_node = queue.remove();
- for(int next_node = 0; next_node < friends[current_node].length();next_node++){
- if(!visisted[next_node] && friends[current_node].charAt(next_node) == 'Y'){
- queue.add(next)node);
- visited[next_node] = true;
- }
- }
- }
- disjoint_graphs++;
- }
- }
- return disjoint_graphs;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement