[Java] 백준 11724번 - 양방향 그래프

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

public class s2_11724 {
    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());

        boolean[][] board = new boolean[N][N];
        // 연결 여부 판단
        boolean[] check = new boolean[N];
        // 이미 탐색을 끝낸 숫자인지 판단

        for (int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            board[a][b] = true;
            board[b][a] = true;
        }

        int cnt = 0;
        
        for (int i = 0; i < N; i++){
            if (check[i]) continue;

            cnt++;
            plus(board, check, i);
        }

        System.out.println(cnt);
    }

    public static void plus(boolean[][] board, boolean[] check, int ptr){
        check[ptr] = true;
        for (int i = 0; i < board[ptr].length; i++){
            if (board[ptr][i] && !check[i]) plus(board, check, i);
        }
    }
}

양방향 그래프의 구현