[백준 11724번] 연결 요소의 개수

문제 링크: 11724번 연결 요소의 개수

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

 

BFS 또는 DFS를 평범하게 구현하여 해결할 수 있는 문제이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    /*
    static void dfs(ArrayList<Integer>[] graph, boolean[] visit, int cur) {
        visit[cur] = true;

        for (int n : graph[cur])
            if (!visit[n])
                dfs(graph, visit, n);
    }
     */

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int node;
        int vertex;
        int[] temp;

        temp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        node = temp[0];
        vertex = temp[1];

        ArrayList<Integer>[] graph = new ArrayList[node+1];
        for (int i = 1; i <= node; i++)
            graph[i] = new ArrayList<Integer>();

        for (int i = 0; i < vertex; i++) {
            int u;
            int v;
            temp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            u = temp[0];
            v = temp[1];

            graph[u].add(v);
            graph[v].add(u);
        }

        boolean[] visit = new boolean[node+1];
        int cnt = 0;

        for (int i = 1; i <= node; i++) {
            if (visit[i]) continue;

            cnt++;
            Queue<Integer> q = new LinkedList<>();
            q.offer(i);
            visit[i] = true;

            while (!q.isEmpty()) {
                int cur = q.poll();
                for (int n : graph[cur])
                    if (!visit[n]) {
                        visit[n] = true;
                        q.offer(n);
                    }
            }
        }

        /*
        boolean[] visit = new boolean[node+1];
        int cnt = 0;

        for (int i = 1; i <= node; i++) {
            if (!visit[i]) {
                cnt++;
                dfs(graph, visit, i);
            }
        }
         */

        System.out.println(cnt);
    }
}