[백준] | JAVA, 자바 | 11724번 - 연결 요소의 개수

https://www.acmicpc.net/problem/11724

---

문제 요약 :

1. 정점의 개수 N, 간선의 개수 M 입력받기

2. 입력받은 M 만큼 간선 입력받기

3. 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static boolean[] visited;
    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());

        visited = new boolean[n + 1];

        ArrayList<Integer>[] lists = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            lists[i] = new ArrayList<>();
        }

        // 2. 입력받은 M 만큼 간선 입력받기
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            // 양방향이기 때문에 양쪽에 추가
            lists[x].add(y);
            lists[y].add(x);
        }

        int cnt = 0;

        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                bfs(lists, i);
                cnt++;
            }
        }
        //3. 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성
        System.out.println(cnt);
    }

    private static void bfs(ArrayList<Integer>[] lists, int n) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(n);
        visited[n] = true;

        while (!queue.isEmpty()) {
            int temp = queue.poll();

            for (int next : lists[temp]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.add(next);
                }
            }
        }
    }
}