[백준] 11724 연결요소

문제보기

연결요소는 그냥 하나의 섬? 덩어리? 처럼 생각하면 이해하기 쉽다.

import java.util.*;

public class Main
{
  public static ArrayList<Integer>[] a; //adj-list 
  public static boolean[] check; // check if visited
  public static int cnt;

  // 나는 bfs가 편해 ㅎ
  public static void bfs(int start){
    Queue<Integer> q = new LinkedList<Integer>();
    q.add(start);
    check[start] = true;

    while(!q.isEmpty()){
      int x = q.remove();

      for(int y:a[x]){
        if(check[y] == false){
          check[y] = true;
          q.add(y);
        }
      }
    }
    cnt++;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
		
    // 인접리스트는 항상 이런식으로 받는다 
    a = (ArrayList<Integer>[]) new ArrayList[n+1];
    for(int i = 0 ; i <= n ; i++ ){
      a[i] = new ArrayList<Integer>();
    }

    for(int i = 0 ; i < m ; i++ ){
      int u = sc.nextInt();
      int v = sc.nextInt();
      a[u].add(v);
      a[v].add(u);
    }
    
    check = new boolean[n+1];
    cnt = 0;
		
    // 연결요소는 덩어리 같은 개념이라 뚝뚝 끊길게 뻔함 
    // 그니까 이런식으로 모든 경우에 대해 bfs를 해줘야 연결요소의 갯수를 알아낼 수 있음
    // 모두 방문하는거고, 한 덩어리의 방문이 끝날때마다 cnt가 ++
    for(int i = 0 ; i <= n ; i++){
      if(check[i] == false){
        bfs(i);
      }
    }
    System.out.println(cnt-1);

  }
}