글 읽기 - 질문 게시판의 내용을 확인하고 반례 체크도 다 했는데 자꾸 틀렸다고 나오네요...

dmlghkswq 5년 전 0

반례도 다 확인했는데 틀렸다고 나오는 이유를 모르겠습니다...

조언 부탁드립니다.. ㅜ.ㅜ

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

public class Main {
    // dfs
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int tCount = sc.nextInt(); // test case

        for (int i = 0; i < tCount; i++) {
            int n = sc.nextInt(); // 정점
            int e = sc.nextInt(); // 간선

            boolean[] check = new boolean[n + 1];
            int[] color = new int[n + 1];
            ArrayList<Integer>[] graph = (ArrayList<Integer>[]) new ArrayList[n + 1];
            // 주의 각 노드에 따로 리스트를 생성해줘야함.
            for (int j = 1; j <= n; j++) {
                graph[j] = new ArrayList<Integer>();
            }

            for (int j = 0; j < e; j++) {
                int u = sc.nextInt();
                int v = sc.nextInt();

                //
                graph[u].add(v);
                graph[v].add(u);
            }
            boolean result = true;
            for (int j = 1; j < n + 1; j++) {
                if (!result)
                    break;

                if (color[j] == 0) {
                    color[j] = 1;
                    result = dfs(graph, check, color, j);
                }
            }
            if (result == true) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }

        sc.close();

    }

    public static boolean dfs(ArrayList<Integer>[] graph, boolean[] check, int[] color, int start) {
        boolean flag = true;
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(start);
        int scolor = color[start];

        while (!stack.isEmpty()) {
            int cur = stack.pop();
            check[cur] = true;

            for (int i = 0; i < graph[cur].size(); i++) {
                int next = graph[cur].get(i);
                if (color[cur] == color[next]) {
                    flag = false;
                    return flag;
                }
                if (check[next] == false) {
                    stack.push(next);
                    color[next] = scolor * (-1);
                }
            }
            scolor *= -1;
        }

        return flag;
    }
}

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

문제

문제

출처

ICPC

질문 게시판의 내용을 확인하고 반례 체크도 다 했는데 자꾸 틀렸다고 나오네요...

dmlghkswq 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말