[코딩테스트/백준 알고리즘] 11724번 - 연결 요소의 개수 (Java, 자바 풀이)

문제

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

11724번: 연결 요소의 개수

---

문제 설명

---

문제 풀이

인접 리스트로 표현한 그래프를 너비 우선 탐색(BFS)를 통해 탐색했다.

---

코드

import java.util.*;
import java.io.*;

class Main {
    static Queue<Integer> q = new LinkedList<>();
    static List<List<Integer>> nodes = new ArrayList<>();
    static boolean[] visit = new boolean[1001];

    static void BFS() {
        while(!q.isEmpty()) {
            int s = q.poll();
            if(!visit[s]) {
                visit[s] = true;
                List<Integer> l = nodes.get(s);
                for(int i : l) {
                    q.offer(i);
                }
            }
        }
    }

    public static void main(String[ ] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int count = 0;
        
        for(int i = 0; i <= N; i++) {
            nodes.add(new ArrayList<>());
        }

        while(M-- > 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int i1 = Integer.parseInt(st.nextToken());
            int i2 = Integer.parseInt(st.nextToken());
            nodes.get(i1).add(i2);
            nodes.get(i2).add(i1);
        }

        for(int i = 1; i <= N; i++) {
            if(!visit[i]) {
                q.offer(i);
                BFS();
                count++;
            }
        }

        System.out.println(count);
    }
}