11724번 : 연결 요소의 개수

11724번 : 연결 요소의 개수

* 문제 출처 : 백준 알고리즘

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_11724 {
    static int[][] map;
    static boolean[] visit;
    static int n;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
 
        n = Integer.parseInt(st.nextToken()); //정점의 개수
        int m = Integer.parseInt(st.nextToken()); //간선의 개수
 
        map = new int[n+1][n+1]; //그래프
        visit = new boolean[n+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());
 
            map[x][y] = map[y][x] = 1; //무방향 그래프
        }
        int cnt = 0; //연결된 갯수
 
        //dfs 하는 수 만큼 
        for (int i = 1; i <= n; i++) { //i번째 정점까지
            if (!visit[i]) { //방문하지 않았으면
                cnt++; //갯수 증가
                dfs(i); //다시 dfs
            }
        }
        System.out.println(cnt);
    }
 
    static void dfs(int x) { //x는 정점
        if (visit[x]) { //방문 했을 경우
            return;
        }
        visit[x] = true; //방문 하지 않았다면 방문 여부 O
 
        for (int i = 1; i <= n; i++) {
            if (!visit[i]&&map[i][x]==1) { //방문하지 않았을 경우와 그래프가 1인 경우
                dfs(i); //다시 dfs
            }
        }
    }
}