백준 11724 (연결 요소) - java

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

11724번: 연결 요소의 개수

연결 요소

• 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.
• 또 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.

즉 하나의 그래프를 시작점으로 그래프 탐색을 했을 때의 결과물이 하나의 연결 요소이다.

 

위 그림에서는 연결 요소의 개수가 2개인 것이다.

주의해야 할 점이 단일 요소로 이루어진 그래프(간선이 아무 것도 없는 단일 점)도 하나의 연결 요소라는 것이다.

 

import java.io.*;
import java.util.*;

public class Main {
    static int n= 0;
    static int m= 0;

    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());

        boolean[][] board = new boolean[n+1][n+1];
        boolean[] visit = new boolean[n+1];
        for(int i=1;i<=m;i++)
        {
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            board[start][end] = true;
            board[end][start] = true;
        }

        int count = 0;

        for(int i=1;i<=n;i++)
        {
            if(!visit[i])
            {
                bfs(i,board,visit);
                count = count + 1;
            }
        }

        System.out.println(count);
        br.close();
    }

    static void bfs(int start,boolean[][] board,boolean[] visit)
    {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visit[start] = true;

        while(!q.isEmpty())
        {
            Integer cur = q.poll();

            for(int i=1;i<=n;i++)
            {
                if(i==cur)
                    continue;

                if(board[i][cur] || board[cur][i])
                {
                    if(visit[i]==false) {
                        visit[i] = true;
                        q.add(i);
                    }
                }
            }
        }
    }

}

문제를 해결하는 방법은 간단하다. 그저 그래프 탐색의 횟수가 정답인 것이다.