#11724 : 연결 요소의 개수

풀이방법

사용된 것:

깊이우선탐색(DFS)

 

2022.05.28

정답을 저장할 int형 변수 answer를 선언하고 0으로 초기화한다.

 

1번부터 N번까지의 모든 노드에 대하여,

아직 방문한 적 없는 노드일 경우

answer를 1 증가시키고

해당 노드를 시작점으로 삼아 dfs를 돈다.

 

코드

Java(2022.05.28)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	
	static ArrayList<Integer>[] arr;	//간선 정보 저장용 배열
	static boolean[] visited;	//방문여부 저장용 배열

	static void dfs(int cur) {
		if(visited[cur]) return;
		visited[cur] = true;
		for(int i:arr[cur])dfs(i);
	}
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		//필요한 변수들을 읽어오거나 선언 및 초기화하기
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int answer = 0;	//정답(연결 요소 개수) 저장용 변수
		visited = new boolean[n+1];
		arr = new ArrayList[n+1];
		for(int i=1; i<n+1; i++) arr[i] = new ArrayList<Integer>();
		//간선정보 읽어와서 저장하기
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr[a].add(b);
			arr[b].add(a);
		}
		//깊이우선탐색 하기
		for(int i=1; i<n+1; i++) {
			if(!visited[i]) {
				answer++;
				dfs(i);
			}
		}
		//정답 출력하기
		System.out.print(answer);
	}

}