[백준] 연결 요소의 개수

풀이

연결요소의 개수를 찾는 문제로, 정점 개수만큼 탐색을 하여 방문한 적 없으면 BFS 탐색을 이용하여 풀었다.
그래프 탐색을 물어보는 간단한 문제였다.

코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		ArrayList<ArrayList<Integer>> graph = new ArrayList();

		/* 정점 개수 N 간선 개수 M */
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		for (int i = 0; i < N + 1; i++)
			graph.add(new ArrayList<Integer>());

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());

			graph.get(u).add(v);
			graph.get(v).add(u);
		}
		boolean visit[] = new boolean[N + 1];
		Queue<Integer> q = new LinkedList<>();
		
		int count = 0;
/*각 정점마다 방문하지 않았으면, BFS를 돌린다. */
		for (int i = 1; i < N + 1; i++) {
			if(!visit[i]) {
				count++;
				q.offer(i);
			}
			while(!q.isEmpty()) {
				for(int j : graph.get(q.poll())){
					if(!visit[j]) {
						q.offer(j);
						visit[j] = true;
					}
				}
			}
		}
		System.out.println(count);
	}
}