vov44k

t111540

Feb 1st, 2023
991
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.17 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.ArrayList;
  5. import java.util.LinkedList;
  6. import java.util.StringTokenizer;
  7.  
  8. public class t111540 {
  9.     static LinkedList<Integer> stack = new LinkedList<>();
  10.     static ArrayList<Integer>[] list;
  11.     static int[] visited;
  12.     static ArrayList<ArrayList<Integer>> res;
  13.     static int cur;
  14.  
  15.     static void dfs(int vertex, int colour) {
  16.         stack.addFirst(vertex);
  17.         visited[vertex] = colour;
  18.         while(stack.size()!=0) {
  19.             cur = stack.removeFirst();
  20.             res.get(colour-1).add(cur+1);
  21.             for(int i: list[cur]) {
  22.                 if(visited[i] == 0) {
  23.                     stack.addFirst(i);
  24.                     visited[i] = colour;
  25.                 }
  26.             }
  27.         }
  28.     }
  29.  
  30.  
  31.     public static void main(String[] args) throws IOException {
  32.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  33.         StringTokenizer st = new StringTokenizer(br.readLine());
  34.         int N = Integer.parseInt(st.nextToken());
  35.         int M = Integer.parseInt(st.nextToken());
  36.         int a, b;
  37.         int colour = 1;
  38.         visited = new int[N];
  39.         list = new ArrayList[N];
  40.         res = new ArrayList<>();
  41.         for (int i = 0; i < N; i++) {
  42.             list[i] = new ArrayList<>();
  43.         }
  44.  
  45.         for (int i = 0; i < M; i++) {
  46.             st = new StringTokenizer(br.readLine());
  47.             a = Integer.parseInt(st.nextToken());
  48.             b = Integer.parseInt(st.nextToken());
  49.             list[a-1].add(b-1);
  50.             list[b-1].add(a-1);
  51.         }
  52.  
  53.         for (int i = 0; i < N; i++) {
  54.             if(visited[i] == 0) {
  55.                 res.add(new ArrayList<>());
  56.                 dfs(i, colour);
  57.                 colour++;
  58.             }
  59.         }
  60.  
  61.         System.out.println(colour-1);
  62.         for (int i = 0; i < res.size(); i++) {
  63.             System.out.println(res.get(i).size());
  64.             for (int j = 0; j < res.get(i).size(); j++) {
  65.                 System.out.print(res.get(i).get(j) + " ");
  66.             }
  67.             System.out.println();
  68.         }
  69.     }
  70. }
Advertisement
Add Comment
Please, Sign In to add comment