문제 이해

방향 없는 그래프가 주어질 것이다.
이 때, A ⇒ B로 갈 수 있는 Route가 존재한다면 A와 B는 한 개의 연결요소에 포함된다고 말할 수 있다.

연결 요소의 개수를 구하라.

---

문제 풀이

visit 배열을 생성할 것이다.
boolean형이고, 공간은 정점 개수만큼 존재할 것이다.
이후 visit 배열을 아래와 같이 순회한다.

1. visit이 true일 경우 : 이미 특정 연결 요소에 포함되었다는 의미이므로 무시한다.

2. visit이 false일 경우 : 해당 점이 특정 연결 요소에 포함되지 않았다는 의미이다. 따라서, 해당 점을 시작으로 하는 연결 요소를 새로 생성하고(연결 요소 개수 하나 추가) dfs를 통해 그 점과 연결된 모든 점들의 visit을 true로 바꿔준다.

---

코드

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

public class Main {
	static int N,M;
	static ArrayList<Integer>[] edges;
	static boolean[] visit;
	
	static void dfs(int start) {
		if(visit[start]) return;
		
		visit[start] = true;
		
		for(int end:edges[start]) {
			dfs(end);
		}
	}
	
	public static void main(String[] args) {
		FastReader sc = new FastReader();

		N = sc.nextInt();
		M = sc.nextInt();
		
		edges = new ArrayList[N+1];
		visit = new boolean[N+1];
		
		for(int i =1;i<N+1;i++) {
			edges[i] = new ArrayList<>();
		}
		
		for(int i =0;i<M;i++) {
			int tmp1 = sc.nextInt();
			int tmp2 = sc.nextInt();
			
			edges[tmp1].add(tmp2);
			edges[tmp2].add(tmp1);
		}
		
		int ans = 0;
		for(int i =1;i<N+1;i++) {
			if(!visit[i]) {
                // 방문한 적이 없다. 
                // 어떤 연결 요소에 포함되지 않았으므로 개수 하나 추가 & DFS
				dfs(i);
				ans++;
			}
		}
		System.out.println(ans);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과