백준_11724 연결요소의 개수 (DFS)Algorithm/Algorithm 문제2024. 1. 19. 23:45
Table of Contents
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class BJ_11724 {
static ArrayList<Integer>[] arr;
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int i, u, v;
int result = 0;
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
arr = new ArrayList[n+1];
visited = new boolean[n+1];
for(i=1; i<n+1; i++) {
arr[i] = new ArrayList<Integer>();
}
for(i=0; i<m; i++) {
st = new StringTokenizer(br.readLine(), " ");
u = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
arr[u].add(v);
arr[v].add(u); //양방향 에지니 양쪽에 추가하는 걸 잊지말자
}
for(i=1; i<n+1; i++) {
if(visited[i] == false) {
result++;
dfs(i);
}
}
System.out.println(new StringBuilder().append(result));
}
static void dfs(int node) {
visited[node] = true;
for (int i : arr[node]) {
if(visited[i] == false) {
dfs(i);
}
}
}
}
'Algorithm > Algorithm 문제' 카테고리의 다른 글
백준_13023 ABCDE (DFS) (0) | 2024.01.21 |
---|---|
백준_2023 신기한 소수 (DFS) (0) | 2024.01.20 |
백준_10989 수 정렬하기3 (기수정렬) - 성공(풀이 참고) (0) | 2024.01.18 |
백준_10989 수 정렬하기 3 (기수 정렬) - 실패(메모리초과) (0) | 2024.01.18 |
백준_1517 버블 소트 (병합정렬) (0) | 2024.01.17 |
@kjyyjk :: 녕의 학습 기록
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!