[Algorithm /백준] 연결 요소의 개수

[문제]
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

[입력]
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

[출력]
첫째 줄에 연결 요소의 개수를 출력한다.


[문제 해결 - BFS]

import java.util.Scanner;

public class Main {

	static boolean []visit ;
	static int count = 0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Main ma = new Main();
		
		int M = sc.nextInt();
		int N = sc.nextInt();
		
		visit = new boolean[M+1];
		int [][] arr = new int[M+1][M+1];
		
		//정점 체크 후 연결선 1로 긋기
		for(int i = 0 ; i<  N ; i++) {
			int U = sc.nextInt();
			int V = sc.nextInt();
			
			arr[U][V]=1;
			arr[V][U]=1;
		}
		
		//방문하지 않았다면 방문
		for(int i = 1 ; i<  arr.length ; i++) {
			if(!visit[i]) {
				ma.BFS(arr, i);
				count++;
			}
		}
		System.out.print(count);
	}
	
	//BFS로 방문함
	public void BFS(int [][]arr , int i) {
		visit[i] = true;
		for(int j = 1; j <arr.length; j++) {
			if(!visit[j] && arr[i][j]== 1) {
				BFS(arr,j);
			}
		}
	}
}