[백준] 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);
            }
        }
    }
}