글 읽기 - [JAVA] 게시판 이외의 반례를 찾아주실 수 있나요 ?

tnehd159 3년 전 0

간선이 0인 경우, 간선이 1개인 경우, 정점이 1개인 경우도 해보았습니다.

양방향인 것도 고려하였지만 해결할 수 없었습니다.

혹시 저의 알고리즘 상 문제인가요 ?

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

public class Main {
    public static Queue<Integer> find = new LinkedList<>();
    public static ArrayList<Integer> group = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        if (m == 0)
            bw.write(String.valueOf(n));
        else {
            int[][] list = new int[n+1][n+1];

            for (int i = 0; i < m; i++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                list[x][y] = 1;
                list[y][x] = 1;
            }

            group.add(1);

            for (int i = 1; i < n+1; i++) {
                if (list[1][i] == 1)
                    find.add(i);
            }

            int count = 0;

            while (group.size() != n) {

                find.add(findMinimum(group, n));

                while (! find.isEmpty()) {
                    int removedElement = find.remove();
                    if (! group.contains(removedElement))
                        group.add(removedElement);

                    for (int i = 1; i < n + 1; i++) {
                        if (list[removedElement][i] == 1 && ! group.contains(i)) {
                            find.add(i);
                            group.add(i);
                        }
                    }
                }
                count++;
                Collections.sort(group);
            }

            bw.write(String.valueOf(count));
        }
        bw.flush();
    }

    public static int findMinimum(ArrayList<Integer> arr, int n) {
        int answer = 0;

        for (answer = 0; answer < n; answer++) {
            if (arr.size() <= answer)
                break;

            if (arr.get(answer) != answer+1)
                break;
        }

        return answer+1;
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[JAVA] 게시판 이외의 반례를 찾아주실 수 있나요 ?

tnehd159 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말