[백준 11724] 연결 요소의 개수 Java 풀이

접근

DFS 또는 BFS를 이용하여 연결 요소의 개수를 구합니다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int n, m;
	static boolean[][] graph;
	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());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		graph = new boolean[n + 1][n + 1];
		visited = new boolean[n + 1];

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			graph[u][v] = graph[v][u] = true;
		}

		// dfs를 이용하여 연결 요소의 개수를 구한다.
		int count = 0;
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				visited[i] = true;
				dfs(i);
				count++;
			}
		}

		// 결과 출력
		System.out.println(count);
	}

	static void dfs(int v) {
		for (int i = 1; i <= n; i++) {
			if (graph[v][i] && !visited[i]) {
				visited[i] = true;
				dfs(i);
			}
		}
	}
}