Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.ArrayList;
- import java.util.LinkedList;
- import java.util.StringTokenizer;
- public class t111540 {
- static LinkedList<Integer> stack = new LinkedList<>();
- static ArrayList<Integer>[] list;
- static int[] visited;
- static ArrayList<ArrayList<Integer>> res;
- static int cur;
- static void dfs(int vertex, int colour) {
- stack.addFirst(vertex);
- visited[vertex] = colour;
- while(stack.size()!=0) {
- cur = stack.removeFirst();
- res.get(colour-1).add(cur+1);
- for(int i: list[cur]) {
- if(visited[i] == 0) {
- stack.addFirst(i);
- visited[i] = colour;
- }
- }
- }
- }
- public static void main(String[] args) throws IOException {
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- StringTokenizer st = new StringTokenizer(br.readLine());
- int N = Integer.parseInt(st.nextToken());
- int M = Integer.parseInt(st.nextToken());
- int a, b;
- int colour = 1;
- visited = new int[N];
- list = new ArrayList[N];
- res = new ArrayList<>();
- for (int i = 0; i < N; i++) {
- list[i] = new ArrayList<>();
- }
- for (int i = 0; i < M; i++) {
- st = new StringTokenizer(br.readLine());
- a = Integer.parseInt(st.nextToken());
- b = Integer.parseInt(st.nextToken());
- list[a-1].add(b-1);
- list[b-1].add(a-1);
- }
- for (int i = 0; i < N; i++) {
- if(visited[i] == 0) {
- res.add(new ArrayList<>());
- dfs(i, colour);
- colour++;
- }
- }
- System.out.println(colour-1);
- for (int i = 0; i < res.size(); i++) {
- System.out.println(res.get(i).size());
- for (int j = 0; j < res.get(i).size(); j++) {
- System.out.print(res.get(i).get(j) + " ");
- }
- System.out.println();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment