DFS알고리즘

문제

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

해설

재귀호출사용

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;


import java.util.StringTokenizer;


public class B2178 {
	static int n;
	static int m;
	static int count=0;
	static ArrayList<Integer>[] A;
	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());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		A = new ArrayList[n+1];
		visited= new boolean[n+1];
		for (int i = 1; i <= n; i++) {
			A[i] = new ArrayList<>();		}

		for (int i = 0; i <m; i++) {
			st =new StringTokenizer (br.readLine());
			int a= Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			A[a].add(b);
			A[b].add(a);
			
		}
		for (int i = 1; i <=n; i++) {
			if(!visited[i]) {
				count++;
				dfs(i);
			}
		}
		System.out.println(count);
	
	}
	private static void dfs(int start) {
		if(visited[start]){
			return;
			
		}
		visited[start]=true;
		for (int i : A[start]) {
			if(visited[i]==false) {
				dfs(i);
			}
		}
		
	}
}