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

풀이

그래프 탐색 문제이다. DFS를 활용하면 되며, 연결 요소의 개수가 DFS의 실행 횟수인게 핵심이다.

소스 코드

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

public class 연결요소의개수 {
	static ArrayList<Integer>[] arr;
	static boolean visited[];
	
	public static void main(String[] args) throws Exception {
		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());
		
		arr = new ArrayList[n+1];
		visited = new boolean[n+1];
		
		for (int i = 1; i < n+1; i++) {
			arr[i] = 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());
			
			arr[u].add(v);
			arr[v].add(u);
		}
		int result = 0;
		for (int i = 1; i < n+1; i++) {
			if (!visited[i]) {
				result++;
				dfs(i);
			}
		}
		
		System.out.println(result);
	}
	
	static void dfs(int v) {
		if (visited[v]) {
			return;
		}
		
		visited[v] = true;
		for (int i : arr[v]) {
			if (visited[i] == false) {
				dfs(i);
			}
		}
	}
}

태클 감사합니다.
조언 환영입니다.