Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |
Tags
- 백준 N과 M 자바
- 스택
- 큐
- 알고리즘
- index of
- 스프링부트 도커
- 백준
- 문자열
- StringTokenizer
- 스프링부트 도커로 배포
- 스프링부트 도커 배포
- 버퍼
- Queue
- 자바
- Programmers
- COS Pro
- 삼각형의 완성조건
- 프로그래머스 풀이
- Stack
- 프로그래머스
- 이진수 변환
- lv0
- 오름차순 정렬
- 프로그래머스 문자열 정렬
- java
- 클라이언트
- SWEA
- 프로그래머스 자바
- Lv1
- lv2
Archives
- Today
- Total
mun dev
[백준] 11724 - 연결 요소의 개수 자바 본문
분류
그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
문제설명
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.
통과한 코드 ✅
import java.util.*;
import java.io.*;
public class Main {
static boolean visited[];
static ArrayList<Integer>[] arr;
public static void main(String[] args) throws IOException {
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());
visited =new boolean[n];
arr=new ArrayList[n];
for(int i=0; i<n; i++){
arr[i]=new ArrayList<Integer>();
}
for(int i=0; i<m; i++){
st=new StringTokenizer(br.readLine());
int s=Integer.parseInt(st.nextToken())-1;
int e=Integer.parseInt(st.nextToken())-1;
arr[s].add(e);
arr[e].add(s);
}
int count=0;
for(int i=0; i<n; i++){
if(!visited[i]){
count++;
dfs(i);
}
}
System.out.println(count);
}
private static void dfs(int v) {
if(visited[v])return;
visited[v]=true;
for(int i:arr[v]){
if(!visited[i]){
dfs(i);
}
}
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 9506 약수들의 합 자바 (0) | 2023.03.26 |
---|---|
[백준] - 1978 소수 찾기 자바 (0) | 2023.03.24 |
[백준] - 2675 문자열 반복 자바 (0) | 2023.03.15 |
[백준] - 11653 소인수분해 자바 (0) | 2023.02.26 |
[백준] - 2501 자바 (0) | 2023.02.25 |