• Scanner를 이용해 입력
• ArrayList<ArrayList<Integer>> 를 이용하여 인접리스트로 그래프를 구현

1. DFS를 이용한 풀이

import java.util.*;

public class Main {

    static ArrayList<ArrayList<Integer>> graph;
    static int[] ch;
    static int answer = 0;
    // DFS
    public static void DFS(int s){
        if(ch[s] == 1)
            return ;
        else{
            ch[s] = 1;
            for(int nv : graph.get(s)){
                if(ch[nv]==0)
                    DFS(nv);
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        graph = new ArrayList<ArrayList<Integer>>();
        ch = new int[n+1];
        for(int i=0; i<n+1; ++i)
            graph.add(new ArrayList<Integer>());
        for(int i=0; i<m; ++i){
            int x = sc.nextInt();
            int y = sc.nextInt();
            graph.get(x).add(y);
            graph.get(y).add(x);
        }
		
        // DFS가 한사이클이 끝날때마다 결과 1증가
        for(int i=1; i<=n; ++i){
            if(ch[i]==0) {
                DFS(i);
                answer++;
            }
        }
        System.out.println(answer);
    }
}

2. BFS를 이용한 풀이

import java.util.*;

public class Main {

    static ArrayList<ArrayList<Integer>> graph;
    static int[] ch;
    static int answer = 0;
    // BFS
    static void BFS(int s){
        Queue<Integer> q = new LinkedList<>();
        q.offer(s);
        while(!q.isEmpty()){
            int len = q.size();
            for(int i=0; i<len; ++i){
                int v = q.poll();
                for(int nv : graph.get(v)){
                    if(ch[nv] == 0){
                        ch[nv] = 1;
                        q.offer(nv);
                    }
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        graph = new ArrayList<ArrayList<Integer>>();
        ch = new int[n+1];
        for(int i=0; i<n+1; ++i)
            graph.add(new ArrayList<Integer>());
        for(int i=0; i<m; ++i){
            int x = sc.nextInt();
            int y = sc.nextInt();
            graph.get(x).add(y);
            graph.get(y).add(x);
        }

		// BFS 한사이클이 돌면 결과 1증가
        for(int i=1; i<=n; ++i){
            if(ch[i]==0) {
                BFS(i);
                answer++;
            }
        }
        System.out.println(answer);
    }
}