[DFS] 연결 요소의 개수(백준 11724번, 자바)

연결 요소(Connected Component) (velog.io)

연결 요소(Connected Component)

 

11724번: 연결 요소의 개수 (acmicpc.net)

11724번: 연결 요소의 개수

 

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	static ArrayList<Integer>[] arr;
	static int N,M;
	static boolean[] visit;
	
	public static void main(String[] args) {
		
		
		Scanner sc=new Scanner(System.in);
		
		N=sc.nextInt();
		M=sc.nextInt();
		
		arr=new ArrayList[N+1];
		
		for(int i=1;i<=N;i++) {
			arr[i]=new ArrayList<>();
		}
		int answer=0;
		for(int i=0;i<M;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			arr[a].add(b);
			arr[b].add(a);
		}
		
		visit=new boolean[N+1];
		
		for(int i=1;i<=N;i++) {
			if(!visit[i]) {
				answer++;
				visit[i]=true;
				dfs(i);
			}
		}
		System.out.println(answer);
	}
	
	static void dfs(int x) {	
		for(int i=0;i<arr[x].size();i++) {
			if(!visit[arr[x].get(i)]) {
				visit[arr[x].get(i)]=true;
				dfs(arr[x].get(i));
			}
		}
	}
}