[백준:11724] 연결 요소의 개수 - JAVA

import java.util.Scanner;

public class Main {

	static int N; //정점의 개수 
	static int M; //간선의 개수
	static boolean visits[];
	static boolean map[][];
	
	public static void main(String[] args) {
		
		int count = 0;
		Scanner scan = new Scanner(System.in);
		
		N = scan.nextInt();
		M = scan.nextInt();
		visits = new boolean[N + 1];
		map = new boolean[N + 1][N + 1];
		
		for(int i = 1; i <= M; i++) { 
			int t1 = scan.nextInt();
			int t2 = scan.nextInt();
			
			map[t1][t2] = true;
			map[t2][t1] = true;
		}
		
		for(int i = 1; i <= N; i ++) {
			if(!visits[i]) {
				dfs(i);
				count++;
			}
		}
		
		System.out.println(count);
		scan.close();
	}
	public static void dfs(int start) {
		
		visits[start] = true;
		
		for(int i = 1; i <= N; i++) {
			if(map[start][i] && !visits[i]) {
				dfs(i);
			}
		}
	}
}

 

 

간선이 이어져있는지의 구분은 bfs와 dfs로 알 수 있다

bfs가 몇번 호출이 되는지 체크하면 알 수 있다.

 

예제1은 덩이가 2개여서 2가 출력

예제2는 하나로 다 간선이 이어져있어서 덩이가 1개여서 1이 출력