[백준 11724]연결 요소의 개수 - 자바

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

1. 풀이

---

연결요소의 개수를 찾는 문제로, 정점의 개수만큼 루프를 돌며 방문한 적이 없는 정점이면 dfs나 bfs를 해주면서 count해주면 되는 문제입니다. 저는 dfs를 통해 풀이를 하였습니다. 

 

2. 코드

---

import java.util.*;

public class Main {
	
	static int[][] graph = new int[1001][1001];
	static int V;
	static int E;
	static boolean[] visited = new boolean[1001];
	
	public static void dfs(int index) {
		if(visited[index] == true)
			return;
		else {
			visited[index] = true;
			for(int i = 1; i <= V; i++) {
				if(graph[index][i] == 1) {
					dfs(i);
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in); 
		
		V = sc.nextInt();
		E = sc.nextInt();
		
		int a,b;
		for(int i = 0; i < E; i++) {
			a = sc.nextInt();
			b = sc.nextInt();
			
			// 간선 연결
			graph[a][b] = graph[b][a] = 1;
		}
		
		int result = 0 ;
		
		// dfs 탐색
		for(int i = 1; i <= V; i++) {
			if(visited[i] == false) { // 방문한 적 없는 노드라면 dfs.
				dfs(i);
				result++;
			}
		}
		
		System.out.println(result);
		
		sc.close();
		return;
	}
}