묻고 답해요
129만명의 커뮤니티!! 함께 토론해봐요.
인프런 TOP Writers
-
해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
강사님 안녕하세요! 깊이 우선 탐색 2 (백준 24480)에서 제공하는 풀이 코드에서 궁금한 점이 있어서 질문 드립니다!
import java.util.*; import java.io.*; class Main { final static int MAX = 100000 + 10; static ArrayList<Integer>[] graph; static boolean[] visited; static int N, M, R; static int[] answer; static int order; public static void dfs(int idx){ visited[idx] = true; answer[idx] = order; order++; for(int i = 0; i < graph[idx].size(); i++){ int next = graph[idx].get(i); if(visited[next] == false) dfs(next); } } public static void main(String[] args) throws IOException{ // 0. 입력 및 초기화 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); R = Integer.parseInt(st.nextToken()); // 1. graph에 연결 정보 채우기 graph = new ArrayList[MAX]; for(int i = 1; i <= N; i++) graph[i] = new ArrayList<>(); visited = new boolean[MAX]; answer = new int[MAX]; order = 1; for(int i = 0; i < M ;i++){ st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()); int y = Integer.parseInt(st.nextToken()); graph[x].add(y); graph[y].add(x); } // 2. 오름차순 정렬 for(int i = 1; i <= N; i++) Collections.sort(graph[i], Collections.reverseOrder()); // 3. dfs(재귀함수 호출) dfs(R); // 4. 출력 for(int i = 1; i <=N; i++){ bw.write(String.valueOf(answer[i])); bw.newLine(); } bw.close(); br.close(); } } 위 제공 답안 코드에서Collections.reverseOrder()위 처럼 revserOrder()를 걸어주신게 잘못 작성된 내용 같은데 혹시 제가 잘못 확인한걸까요?일단 해당 코드로 그대로 백준에 올리면 안되고 있는 상태입니다!그리고 answer나 visited에 MAX를 넣으시는 이유가 궁급합니다! 방문정보나 answer의 경우 N+1로도 초기화가 가능하지 않나요? 혹시 더 복잡한 문제등에서 풀이의 간결성을 위해 필요한 방법일까요?? --강의 너무 잘 보고 있습니다! 훌륭한 강의 찍어주셔서 감사합니다!
-
해결됨[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편
[바닥장식][런타임에러] 질문 있습니다.
강사님이 작성해주신 코드로 실행을 해봤을때 런타임 에러가 발생합니다. 제가 코드를 잘못 작성한 걸까요?import sys sys.setrecursionlimit(10**6) inpurt = sys.stdin.readline def dfs(y, x): global map_ cur = map_[y][x] map_[y][x] = "" if cur == "-" and map_[y][x + 1] == "-": dfs(y, x + 1) elif cur == "|" and map_[y + 1][x] == "|": dfs(y + 1, x) # 1. initialize N, M = map(int, input().split()) MAX = 50 + 10 # N * M map_ = [["" * MAX] for _ in range(MAX)] # 2. connection info for i in range(1, N + 1): row = input() for j in range(1, M + 1): map_[i][j] = row[j - 1] # 3. dfs answer = 0 for i in range(1, N + 1): for j in range(1, M + 1): if map_[i][j] != "": dfs(i, j) answer += 1 # 4. print print(answer)코드에 오타가 있는 것 같습니다 map -> map_
-
해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
촌수 계산
count라는 매개변수를 같이 전달해주기 보다 dfs가 호출될 때마다 answer를 넣어주는 방식으로 풀어봤는데 왜인지 end 값을 찾았을 때 return이 적용이 안되는 거 같습니다. 혹시 어떤 문제가 있는지 봐주실 수 있나요? import java.util.*; import java.io.*; class Main { static int N, start, end, M; static boolean[] visited; static ArrayList<Integer>[] graph; static int answer = -1; private static void dfs(int i) { if (i == end) { System.out.println("end: " + end); return; } visited[i] = true; for (int j = 0; j < graph[i].size(); j++) { int next = graph[i].get(j); if (visited[next] == false) { System.out.println("next: " + next); dfs(next); answer++; } } } public static void main(String[] args) throws IOException{ // 입력 및 초기화 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); N = Integer.parseInt(br.readLine()); // 노드의 개수 StringTokenizer st = new StringTokenizer(br.readLine()); start = Integer.parseInt(st.nextToken()); // 시작 노드 end = Integer.parseInt(st.nextToken()); // 끝 노드 System.out.println(end); M = Integer.parseInt(br.readLine()); // 간선의 개수 visited = new boolean[N+1]; // graph 선언 후 초기화 graph = new ArrayList[N+1]; for (int i = 1; i <= N; i++) { graph[i] = new ArrayList<>(); } for (int i = 1; i <= M; i++) { st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()); int y = Integer.parseInt(st.nextToken()); graph[x].add(y); graph[y].add(x); } System.out.println(Arrays.toString(graph)); // dfs 호출 dfs(start); System.out.println(answer); bw.close(); br.close(); } }
-
해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
연결 요소의 개수 (백준 11724)
강의 영상마다 질문이 있으면 언제든 그리고 바로 질문 남겨주세요! 질문할 때 가장 정확하게 이해할 수 있습니다.해당 영상과 관련된 질문들을 해주실 때 제가 가장 정확히 답변 드릴 수 있습니다!취업 전반의 상담이나, "제 코드가 왜 틀렸는지 알려주세요"와 같이 광범위한 질문은, 질문자의 상황에 따라 답변이 달라질 수 있기 때문에, 정확한 답변을 드리기가 어렵습니다 :(이런 분들을 위해서는 멘토링 항목으로 별도 제공하고 있으니, 다음 링크를 참고해주세요!이 링크를 통해서는 본인의 코드가 왜 틀렸는지 모를 때 질문을 주셔도 좋고, 취업 전반(면접 준비, 자소서, CS 면접 등)에 관련한 질문을 주시면 답변 드리겠습니다 :)"이 질문은 해도 되나?"라는 생각이 드신다면 우선 남겨주세요! 제가 답변 드리기 어려운 건 멘토링에 올려 달라고 재요청 드리겠습니다 :)1. 저번 강의에서 풀이하신 것처럼 이번 강의에도 재귀 함수의 depth를 그려보았는데 맞나요?2. 혹시 CS 면접 관련해서 대략 어떻게 준비해야 하는지 질문 드려도 되나요?
-
해결됨[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편
그래프 짤 때 adjacency matrix vs adjacency list
안녕하세요 정말 강의 잘 듣고 있습니다. 저는 코딩을 영어로 공부하고 있는데 지금까지 봤던 문제들 중에서 graph 를 짜는 부분에서 adjacency matrix 와 adjacency list 두 종류를 쓰셨는데 강의에서 말씀하신 부분을 보면 모든 면에서 adjacency list 가 더 낫지 않나요? 특히나 메모리를 적게 쓰는 부분과 더 짜기가 쉽다는 부분에 있어서요. adjacency marix 가 adjacency list 보다 선호되는 케이스가 혹시 있는지 궁금해서 질문 드립니다. 그리고 adjacency list 를 만드실 때 리스트 안에 리스트를 만드는 설정을 하셨는데 혹시 해시맵에 리스트를 넣어서 하는 게 더 보편적인건가요?추가) 아 그리고 visited 는 list 에 False 로 채워넣는것 대신에 set() 으로 하는 게 더 메모리에 좋을까요?
-
해결됨[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편
2644문제(촌수 구하기) 질문입니다.
1) 이 문제는 2차월 배열에 False로 초기화한다음 입력받은값만 True로 썼는데 이 문제도 메모리 낭비를 위해 빈 리스트에 넣어서 풀려면 어떻게 해야 할까요?? 2) 재귀(1)중간에 재귀(2)타고 여기서 재귀(3)타고 재귀(4)타서 값을 찾았을때 리턴을 했는데요 리턴을 했다고 해서 1,2,3번의 반복문을 break하는건 아니더라고요 어짜피 답은 찾았으니 시간낭비 방지를 위해 반복문을 돌지 않는방법이 있나요?
-
해결됨[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편
DFS 문제 하나 여쭤봅니다!..
강의를 들어보다가 백준 - 16964번 DFS 스페셜 저지 문제를 풀어 보았는데 여러개의 답이 나올 수 있는 경우를 특정하기가 어려줘 질문 남겨봅니다!..graph에서 순차적으로 나오는 경우는 답을 구할 수 있는데 그래프에서 랜덤한 방향으로 진행될 시 어떻게 해야되는지 궁금합니다!..제가 짜본 기본 코드입니다..ㅜㅜ 도움 부탁드립니다!import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline # 함수 def dfs(idx): global visited, answer, graph, order visited[idx] = True answer[idx] = order order += 1 for i in graph[idx]: if not visited[i]: dfs(i) # 0. 입력 조건 N = int(input()) visited = [False] * (N+1) answer = [0] * (N+1) order = 1 graph = [[] for _ in range(N+1)] # 1. 그래프 받아오기 for _ in range(N-1): x, y = map(int, input().split()) graph[x].append(y) graph[y].append(x) # 2. dfs 수행 dfs(1) # 3. 출력하기 given = list(map(int, input().split())) # answer.sort() answer = answer[1:] if given == answer: print(1) else: print(0)
-
해결됨[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편
다음강의
언제나오나요? DP 강의 보고싶네여..
-
해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
백준 24479 문제 시간 초과 질문 드려요
안녕하세요 백준에서 테스트 결과 시간 초과 오류가 납니다 . 확인 한번 가능할까요?import java.io.*; import java.util.*; public class Main { static final int MAX = 100000 + 10; static int N, M, R; static ArrayList<Integer>[] graph; static boolean[] visited; static int[] answer; static int order; public static void dfs(int idx) { visited[idx] = true; answer[idx] = order; order++; for (int i = 0; i < graph[idx].size(); i++) { int next = graph[idx].get(i); if (visited[next] == false) dfs(next); } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); R = Integer.parseInt(st.nextToken()); graph = new ArrayList[MAX]; for (int i = 1; i <= N; i++) { graph[i] = new ArrayList<>(); visited = new boolean[MAX]; answer = new int[MAX]; order = 1; } for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()); int y = Integer.parseInt(st.nextToken()); graph[x].add(y); graph[y].add(x); } for (int i = 1; i <= N; i++) { Collections.sort(graph[i]); } dfs(R); for (int i = 1; i <= N; i++) { bw.write(String.valueOf(answer[i])); bw.newLine(); } bw.close(); br.close(); } }
-
해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
백준 실행시 틀립니다.
안녕하세요 강사님. 문제를 풀고 백준에 제출했을 때 계속 오답으로 나와 질문 드립니다..제가 봤을 때 강사님 코드랑 거의 비슷하게 수정까지 한 것 같은데.. 어떤 부분이 잘못되었는지 확인 한번 부탁드립니다.import java.io.*; import java.util.StringTokenizer; public class Main { final static int MAX = 50 + 10; static boolean map[][]; static boolean visited[][]; /* static int dirY[] = {1, 1, 1, 0, 0, -1, -1, -1}; static int dirX[] = {-1, 0, 1, -1, 1, -1, 0, 1};*/ static int dirY[] = {-1, -1, 0, 1, 1, -1, 0, -1}; static int dirX[] = {0, 1, 1, -1, 0, -1, -1, -1}; static int N, M; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); while (true) { StringTokenizer st = new StringTokenizer(br.readLine()); M = Integer.parseInt(st.nextToken()); // 너비 x N = Integer.parseInt(st.nextToken()); // 높이 y if (N == 0 && M == 0) break; map = new boolean[MAX][MAX]; visited = new boolean[MAX][MAX]; // 1. map 정보 반영 for (int i = 1; i <= N; i++) { st = new StringTokenizer(br.readLine()); for (int j = 1; j <= M; j++) { map[j][i] = Integer.parseInt(st.nextToken()) == 1; } } // 2. dfs int result = 0; for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { if (map[i][j] && !visited[i][j]) { dfs(i, j); result++; } } } // 3. 출력 bw.write(String.valueOf(result)); bw.newLine(); } bw.close(); bw.close(); } private static void dfs(int y, int x) { visited[y][x] = true; for (int i = 0; i < 8; i++) { int newY = dirY[i] + y; int newX = dirX[i] + x; if (map[newY][newX] && !visited[newY][newX]) { dfs(newY, newX); } } } }
-
해결됨[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편
알고리즘 수업 - 깊이 우선 탐색 2( 백준 24480) 번 질문
강의 제목 : 알고리즘 수업 - 깊이 우선 탐색 2( 백준 24480) 번 질문 안녕하세요! 위 강의 10:14번에 나와있는 정리 노트 관련해서 하나 여쭤보고 싶은 것이 있어요! 5번 '방문 순서를 담기 위해서는 어떤 자료구조를 사용해야 될까?' 이거 답이 리스트(LIST) 인가요?? 혹시 이 정리 노트에 있는 질문 5개에 대한 답변이 적혀있는 PDF 같은 게 있을까요??나중에 자격증 공부할 때 도움될 것 같아서 여쭤봅니다 감사합니다! 강의 영상마다 질문이 있으면 언제든 그리고 바로 질문 남겨주세요! 질문할 때 가장 정확하게 이해할 수 있습니다.해당 영상과 관련된 질문들을 해주실 때 제가 가장 정확히 답변 드릴 수 있습니다!취업 전반의 상담이나, "제 코드가 왜 틀렸는지 알려주세요"와 같이 광범위한 질문은, 질문자의 상황에 따라 답변이 달라질 수 있기 때문에, 정확한 답변을 드리기가 어렵습니다 :(이런 분들을 위해서는 멘토링 항목으로 별도 제공하고 있으니, 다음 링크를 참고해주세요!이 링크를 통해서는 본인의 코드가 왜 틀렸는지 모를 때 질문을 주셔도 좋고, 취업 전반(면접 준비, 자소서, CS 면접 등)에 관련한 질문을 주시면 답변 드리겠습니다 :)"이 질문은 해도 되나?"라는 생각이 드신다면 우선 남겨주세요! 제가 답변 드리기 어려운 건 멘토링에 올려 달라고 재요청 드리겠습니다 :)
-
해결됨[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편
1260 문제 풀이에서는 함수 global로 변수 선언
유형1 문제 풀이에서는 함수 선언에서 global visited, graph 로 선언해줬는데, 왜 여기서는 안하신건가요?
-
해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
재귀대신 스택으로 구현하면 안될까요?
이 문제의 재귀는 이해가 됬지만, 다른 문제들에서 마주치는 재귀함수들은 손이 잘 안가고, 항상 남의코드를 봐야만 이해가 되더라구요.여기서 dfs함수를 스택으로 구현하면 라인이 더 길어져 재귀보다는 깔끔하지가 않은데, 이해 및 구현이 쉬운거 보다 명확한거 같은데, 코딩테스트의 재귀들은 모두 스택으로 구현하면 어떨지 궁금합니다.
-
해결됨[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편
PyPy3와 Python3
백준에서 bfs와 dfs 관련 문제를 추가적으로 풀다보니까, Python3에서는 시간 초과를 해결되지 않는 문제가, PyPy3에서는 해결되는 경우가 있습니다.이럴 때는 Python3에서도 해결 가능하도록 시간 복잡도를 줄이기 위해 노력해야 할까요?아니면 PyPy3 환경에서 정답임을 만족해야 할까요...?
-
해결됨[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편
백준 2606
안녕하세요 선생님! 복습하다가 의문점이 생겨 질문드립니다.from collections import defaultdict N = int(input()) T = int(input()) dic = defaultdict(list) discovered = [] for _ in range(T): a, b = map(int, input().split()) dic[a].append(b) dic[b].append(a) def dfs(node): global dic, discovered discovered.append(node) for n in dic[node]: if n not in discovered: dfs(n) return dfs(1) print(len(discovered) - 1)이 코드에서 dic[b].append(a)를 지워도 문제 해결에는 영향이 없어 보이는데, 백준에 제출하면 틀린 답으로 나옵니다.즉, 그래프를 양방향이 아닌 단방향으로 설정해도 문제 없지 않나요..?
-
해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
dfs 매개변수에서 y,x 를 왜 순서를 반대로 쓰셨는지 궁금합니다.
점프왕 젤리문제에서 dfs 메서드에 dfs(int x, int y)가 아닌 dfs(int y, int x)인지 궁금합니다!이전 문제부터 계속 궁금해했는데, 왜 순서를 바꾸셨는지에 대한 명확한 이유를 못찾겠어서 질문올렸습니다.// 점프왕 젤리 import java.util.*; import java.io.*; class Jump_king_jelly { static final int MAX = 3 + 100 + 10; static int map[][]; static boolean visited[][]; static int N; static int dirY[] = {1, 0}; static int dirX[] = {0, 1}; public static void dfs(int y, int x) { visited[y][x] = true; if(y == N && x == N) return; for(int i = 0; i < 2; i++) { int newY = y + dirY[i] * map[y][x]; int newX = x + dirX[i] * map[y][x]; if(visited[newY][newX] == false) { dfs(newY, newX); } } } public static void main(String[] args) throws IOException { // 0. 입력 및 초기화 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); N = Integer.parseInt(br.readLine()); map = new int[MAX][MAX]; visited = new boolean[MAX][MAX]; // 1. map에 정보 반영 for(int i = 1; i <= N; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); for(int j = 1; j <= N; j++) { map[i][j] = Integer.parseInt(st.nextToken()); } } // 2. dfs 수행 dfs(1,1); // 3. 출력 if(visited[N][N]) bw.write("HaruHaru"); else bw.write("Hing"); bw.close(); br.close(); } }
-
해결됨[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편
22479번 문제 런타임 에러 도와주세요 ㅠㅠ
24479번, 강의 사진과 같이 아래 링크처럼 파이썬으로 코딩했는데, 런타임 에러가 나고 있어요 ㅠㅠ 도와주세요 https://www.acmicpc.net/source/70097735 강의 영상마다 질문이 있으면 언제든 그리고 바로 질문 남겨주세요! 질문할 때 가장 정확하게 이해할 수 있습니다.해당 영상과 관련된 질문들을 해주실 때 제가 가장 정확히 답변 드릴 수 있습니다!취업 전반의 상담이나, "제 코드가 왜 틀렸는지 알려주세요"와 같이 광범위한 질문은, 질문자의 상황에 따라 답변이 달라질 수 있기 때문에, 정확한 답변을 드리기가 어렵습니다 :(이런 분들을 위해서는 멘토링 항목으로 별도 제공하고 있으니, 다음 링크를 참고해주세요!이 링크를 통해서는 본인의 코드가 왜 틀렸는지 모를 때 질문을 주셔도 좋고, 취업 전반(면접 준비, 자소서, CS 면접 등)에 관련한 질문을 주시면 답변 드리겠습니다 :)"이 질문은 해도 되나?"라는 생각이 드신다면 우선 남겨주세요! 제가 답변 드리기 어려운 건 멘토링에 올려 달라고 재요청 드리겠습니다 :)
-
해결됨[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편
11724 문제 질문
안녕하세요. 공부하다가 또 질문이 생겨 다시 한 번 질문 드립니다...리스트를 조회하는 것보다 딕셔너리를 조회하는 것이 더 빠를 거 같아서 문제의 그래프를 딕셔너리 자료형으로 바꿔주고 있는데요.제가 작성한 코드가 로컬에서 예시를 넣었을 때는 잘 되는데 백준에서는 틀린 답이라고 나옵니다..코드를 첨부하여 질문 드리고 싶은데, 멘토링 부분이 어디있는지 알려주시면 감사하겠습니다!
-
해결됨[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편
그래프 초기화
안녕하세요. 선생님 덕분에 멋진 강의를 듣고 있는 학생입니다.이제 유형 1을 다 수강했는데, graph를 초기화할 때 보통 N의 개수가 적으면 불리언 2차원 배열로 선언하고, N의 개수가 많으면 빈리스트로 구성된 2차원 리스트로 선언하는데요.그냥 모든 문제에 빈리스트로 구성된 2차원 배열을 선언하지 않는 이유가 N의 개수가 적으면 배열로 선언하고 조회하는 게 더 빠르기 때문인지 여쭤봐도 될까요?
-
해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
안녕하세요 11724번 질문드려요!
안녕하세요! 강의 수강 중 질문이 있어 질문 드립니다.현재 이런식으로 코드를 작성했고, 백준 스타일에 맞춰 제출을 했는데 오답처리가 되었습니다. 디버깅 시에도 1번예제6 5 1 2 2 5 5 1 3 4 4 6이걸 입력했을 때 2가 나오는 것이 아닌 dfs를 호출시 if절에서 전부 vistied[i] 부분이 false처리가 되어서 입력한 크기인 6이 answer로 계속 출력되고 있습니다.어느 부분이 문제여서 계속 찾고 있지만 발견하지 못하여 질문드립니다.package algorithmstudy.dfs; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class boj11724 { final static int MAX = 1000 + 10; static boolean[][] graph; static boolean[] visited; static int N, M; static int answer; static void dfs(int idx) { visited[idx] = true; for (int i = 1; i <= N; i++) { if (!visited[idx] && graph[idx][i]) { dfs(i); } } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); // 1. graph에 연결 정보 채우기 graph = new boolean[MAX][MAX]; visited = new boolean[MAX]; for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); graph[u][v] = true; graph[v][u] = true; } for (int i = 1; i <= N; i++) { if (!visited[i]) { answer++; dfs(i); } } bw.write(String.valueOf(answer)); br.close(); bw.close(); } }