백준_연결 요소의 개수_11724

//알고리즘

1. 그래프탐색

 -> 인접리스트를 만들어 탐색

 -> 모든 정점에서 탐색, 연결되어있는 노드는 방문체크해서 다시 탐색하지 않음.

 

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

public class 연결요소의개수_11724 {
	static int N, M, ans;
	static boolean[] v;
	static ArrayList<Integer>[] list;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		list = new ArrayList[N + 1];
		v = new boolean[N + 1];
		for (int i = 0; i <= N; i++) {
			list[i] = new ArrayList<Integer>();

		}

		int start, end;
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			start = Integer.parseInt(st.nextToken());
			end = Integer.parseInt(st.nextToken());

			list[start].add(end);
			list[end].add(start);
		}

		for (int i = 1; i < list.length; i++) {
			if (!v[i]) {
				ans++;
				dfs(i);
			}
		}

		System.out.println(ans);
	}

	private static void dfs(int idx) {
		v[idx] = true;
		int size = list[idx].size();
		for (int i = 0; i < size; i++) {
			if (!v[list[idx].get(i)]) {
				dfs(list[idx].get(i));
			}

		}

	}

}

 

※ 문제를 꼼꼼히 읽지 않아서 3번이나 틀렸던 문제.. 쉬운 문제일수록 꼼꼼히 풀자!