글 읽기 - JAVA_IndexOutofBounds 에러입니다 ㅜㅜ

bsu1209 2년 전 0

방문 여부와 순서를 discovered에 저장하는 방식이고,

홀수 개의 정점들이 cycle을 이루면, 이분그래프가 될 수 없다고 판단하여 작성하였습니다 ...!

보이는 반례들은 모두 맞는데, 자꾸 IndexOutofBounds가 뜨네요 ㅜㅠ

확인 부탁드립니다 ... !!!! ㅜㅜㅜ

import java.util.ArrayList;
import java.util.Scanner;

class Graph {
    private final ArrayList<ArrayList<Integer>> graph;
    private int[] discovered;
    private boolean oddCycle = false;
    private int dis;

    public Graph(int size) {
        this.graph = new ArrayList<>();

        for (int i = 0; i <= size; i++) {
            graph.add(new ArrayList<>());
        }
    }

    public void DoubleAdd(int x, int y) {
        graph.get(x).add(y);
        graph.get(y).add(x);
    }

    public boolean isOddCycle(int s, int n) {
        discovered = new int[20001];
        dis = 1;
        this.dfs(s, n);
        return this.oddCycle;
    }

    public void dfs(int parent, int now) {
        discovered[now] = dis++;
        if (!graph.isEmpty()) {
            int size = graph.get(now).size();
            for (int i = 0; i < size; i++) {
                if (!graph.get(now).isEmpty()) {
                    int idx = graph.get(now).get(i);
                    if (discovered[idx] == 0) {
                        this.dfs(now, idx);
                    }
                    else if (idx != parent && ((discovered[now] - discovered[idx])%2 == 0)) {
                        this.oddCycle = true;
                    }
                }
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        while (T > 0) {
            int v = sc.nextInt();
            int e = sc.nextInt();
            sc.nextLine();
            boolean isOdd = false;

            Graph g = new Graph(v);

            for (int i = 0; i < e; i++) {
                String str = sc.nextLine();
                int a = str.charAt(0) - '0';
                int b = str.charAt(2) - '0';

                g.DoubleAdd(a,b);
            }

            for (int i = 1; i <= v; i++) {
                isOdd = g.isOddCycle(i, i);
                // odd가 한 번이라도 true면 이분 그래프가 될 수 없다.
                if (isOdd)
                    break;
            }

            if (!isOdd)
                System.out.println("YES");
            else
                System.out.println("NO");
            T-=1;
        }

        sc.close();
    }
}

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

문제

문제

출처

ICPC

JAVA_IndexOutofBounds 에러입니다 ㅜㅜ

bsu1209 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말