Advertisement
vov44k

t111839

Jan 26th, 2023 (edited)
432
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.05 KB | None | 0 0
  1. import java.util.LinkedList;
  2. import java.util.Scanner;
  3.  
  4. public class t111839 {
  5.  
  6.     public static void BFS_comp(int[][] g, int n){
  7.         LinkedList queue = new LinkedList<Integer>();
  8.         int[] d = new int[n];
  9.         String res = "";
  10.         int quantity = 0;
  11.         for (int i=0;i<n;i++)
  12.             d[i]=-1;
  13.         for(int j=0;j<n;j++) {
  14.             if(d[j]==-1) {
  15.                 String result = "";
  16.                 quantity++;
  17.                 int kol=1;
  18.                 d[j]=0;
  19.                 queue.addLast(j);
  20.                 while (!queue.isEmpty()){
  21.                     int v = (int)queue.pollFirst();
  22.                     for (int i=0;i<n;i++){
  23.                         if(g[v][i]==1&&d[i]==-1){
  24.                             d[i]=d[v]+1;
  25.                             queue.addLast(i);
  26.                             kol++;
  27.                         }
  28.                     }
  29.                     result = result + (v+1) + " ";
  30.                 }
  31.                 res = res + kol + "\n" + result + "\n";
  32.             }
  33.         }
  34.         System.out.println(quantity + "\n" + res);
  35.     }
  36.    
  37.     public static void main(String[] args) {
  38.         Scanner sc = new Scanner(System.in);
  39.        
  40.         int n=sc.nextInt();
  41.        
  42.         int[][] matrix  = new int[n][n];
  43.         for(int i=0;i<n;i++) {
  44.             for (int j=0; j<n; j++) {
  45.                 matrix[i][j]=sc.nextInt();
  46.             }
  47.         }
  48.  
  49.         BFS_comp(matrix, n);
  50.     }
  51.  
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement