자바로 백준 11724 풀기

• 실버 1단계 문제

풀이)

연결 요소란 전체 그래프 내 끊어져있는 부분 그래프들의 개수를 말한다.

따라서 DFS가 몇 번 실행되었는지를 파악해야 한다.
DFS가 예를 들어 3번 실행되고 모든 요소를 방문한다면, 연결 요소는 3개이다.

인접 리스트를 사용해 풀 것이다.

인접 행렬 시간 복잡도 O(점^2)
인접 리스트 시간 복잡도 O(간선)
간선이 많으면 행렬, 간선이 적으면 리스트로 구현하면 된다.

내 코드)

// 백준 온라인 저지 11724번

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

public class Main{
	
	static boolean visited[];
	
	static ArrayList<Integer> A[];
	
	static void DFS(int s) {
		//시작점 s에서부터 DFS 탐색한다..
		if(visited[s]) {
			return;
		}
		visited[s] = true;
		for(int i: A[s]) {
			if(!visited[i]) {
				DFS(i);
			}
		}
	}
	
	public static void main(String[]args) throws IOException{
		
		// 입력. 
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		// 방문 여부 체크 배열
		visited = new boolean[N+1];
		
		// 인접 리스트
		A = new ArrayList[N+1];
		for(int i=1;i<=N;i++) {
			A[i] = new ArrayList<Integer>();
		}
		// 노드 삽입
		for(int i=1;i<=M;i++) {
			st = new StringTokenizer(bf.readLine());		
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			A[u].add(v);
			A[v].add(u);
		}
		
		// 숫자 세기
		int count = 0;
		for(int i=1;i<=N;i++) {
			if(!visited[i]) {
				count++;
				DFS(i);
			}
		}
		
		// 출력
		System.out.println(count);
		
	}
}