[Java/백준/DFS] 11724번: 연결 요소의 개수

문제

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

코드

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

class Main{
	static ArrayList<Integer>[] adjacent;
	static boolean[] visited;
	
	public static void dfs(int start) {
		visited[start] = true;
		for(int e : adjacent[start]) {
			if(!visited[e])
				dfs(e);
		}		
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] info = br.readLine().split("\\s");
		int N = Integer.parseInt(info[0]);
		int M = Integer.parseInt(info[1]);
		
		adjacent = new ArrayList[N+1];
		visited = new boolean[N+1];
		
		for(int i=1; i<=N ; i++) {
			adjacent[i] = new ArrayList<Integer>();
		}
		for(int i=0; i<M; i++) {
			String[] strs = br.readLine().split("\\s");
			int a = Integer.parseInt(strs[0]);
			int b = Integer.parseInt(strs[1]);
			adjacent[a].add(b);
			adjacent[b].add(a);
		}
		
		int cnt = 0;
		for(int i=1; i<=N; i++) {
			if(!visited[i]) {
				dfs(i);
				++cnt;
			}
		}
		System.out.println(cnt);
	}
}