백준 11724 풀이

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

오랜만의 그래프 문제이다.

주어진 그래프의 연결 요소를 찾는 문제인데 연결요소가 멀까

위와 같은 그림이 연결 요소이다.

연결 요소가 될 조건은

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

다음과 같고 그래프 문제이기때문에 dfs 혹은 bfs를 적용해서 풀면 간단하게 풀린다.

또 방향없는 그래프이기 때문에 간선을 이어줄 때 주의해야한다. 이 부분을 캐치하지 못해 시간이 끌렸다.

import java.io.*;

public class Main {
    static boolean[] visited;
    static boolean[][] visit;
    static int[] p;
    static int[] ap;
    static int[][] arr;
    static int min = 1001;
    static int n, m;
    static int cnt = 0;
    static int index = 0;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String line = br.readLine();
        String[] nums = line.split(" ");
        n = Integer.parseInt(nums[0]);
        m = Integer.parseInt(nums[1]);

        arr = new int[n + 1][n + 1];
        visit = new boolean[n + 1][n + 1];
        visited = new boolean[n + 1];
        visited[0] = false;
        for (int h = 1; h <= n; h++) {
            visited[h] = false;
            for (int j = 1; j <= n; j++) {
                visit[h][j] = false;
            }
        }

        for (int i = 0; i < m; i++) {
            String str = br.readLine();
            String[] s = str.split(" ");
            arr[Integer.parseInt(s[0])][Integer.parseInt(s[1])] = 1;
            arr[Integer.parseInt(s[1])][Integer.parseInt(s[0])] = 1;
        }
        find();

        bw.write(Integer.toString(cnt));

        br.close();
        bw.close();
    }

    public static void find() {
        for (int i = 1; i <= n; i++) {
            if (visited[i] == false) {
                dfs(i);
                cnt++;
            }
        }
    }

    public static void dfs(int start) {
        visited[start] = true;
        for (int i = 1; i <= n; i++) {
            if (arr[start][i] == 1 && visited[i] == false) {
                dfs(i);
            }
        }
    }
}