[백준11724] 연결 요소 - Connected Component란?

 

 

연결요소란?

Connected Component

1~6까지 모든 요소를 하나의 그래프라고 쳤을 때 위의 그림처럼 나누어져 있는 경우가 있다.

이렇게 나누어진 각각의 그래프를 연결 요소라고 한다.

 

연결 요소의 조건

1. 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.

2. 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.

 

즉 위의 그림은 2개의 연결 요소로 구성된 하나의 그래프이다.

참고로 연결 요소가 1개인 그래프는 연결 그래프라고 한다.

 

-----

백준 11724를 통한 연결 요소 실습

 

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

11724번: 연결 요소의 개수

import java.sql.Array;
import java.util.*;


public class Main {
    static List<Integer>[] arr;
    static boolean[] check;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        arr = new ArrayList[n + 1];
        check = new boolean[n + 1];

        for (int i = 1; i <= n; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            arr[a].add(b);
            arr[b].add(a);
        }

        int result = 0;
        for (int i = 1; i <= n; i++) {
            if (check[i] == true) continue;
            
            bfs(i);
            result++;
        }

        System.out.println(result);
    }

    static void bfs(int node) {
        Queue<Integer> q = new LinkedList<>();

        q.add(node);
        check[node] = true;

        while (!q.isEmpty()) {
            int num1 = q.remove();
            for (int i = 0; i < arr[num1].size(); i++) {
                int num2 = arr[num1].get(i);
                if (!check[num2]){
                    q.add(num2);
                    check[num2] = true;
                }
            }
        }
    }
}