글 읽기 - [java] 게시판의 많은 반례를 확인했지만 왜 틀린지 모르겠습니다 ㅠ

noble5712 3년 전 0

이쯤 되니 문제를 아예 잘못 이해해서 반례를 보고도 맞다고 생각하는건지..ㅜ

현답 부탁드립니다.

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

public class Q1707 {

	static ArrayList<Integer>[] a;
	static boolean[] check;
	static int[] color;
	static int colorcheck;
	static boolean ok = true;
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer s = new StringTokenizer(br.readLine());
		
		int t = Integer.parseInt(s.nextToken());
		
		
		
		while(t-- > 0) {
			
			s = new StringTokenizer(br.readLine());
			
			int v = Integer.parseInt(s.nextToken()), m = Integer.parseInt(s.nextToken());
			
			a = new ArrayList[v+1];
			
			check = new boolean[v+1];
			color = new int[v+1];
			colorcheck = 1;
			
			for(int i = 0; i < a.length; i++) {
				a[i] = new ArrayList<>();
			}
			
			for(int i = 0; i < m; i++) {
				s = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(s.nextToken());
				int y = Integer.parseInt(s.nextToken());
				
				a[x].add(y);
				a[y].add(x);
			}
			 /*for(int i = 0 ; i<a.length;i++) {
		        	System.out.println(" * " + a[i] + " * ");	
		        }*/
			
			for(int i = 1; i < v+1; i++) {
				
				if(!ok) {
					break;
				}
				if(!check[i]) {
					dfs(i,a,colorcheck);
				}
			}
			
			for (int i = 1; i < v+1; i++) {
				for (int j : a[i]) {
					if (color[i] == color[j]) {
						ok = false;
					}
				}
			}
			/*for(int i = 0 ; i<a.length;i++) {
	        	System.out.println(" * " + color[i] + " * ");	
	        }*/
			if(!ok) System.out.println("NO");
			else System.out.println("YES");
		}
		
	}
	
	public static void dfs(int x, ArrayList<Integer>[] a,int colorcheck) {
		check[x] = true;
		color[x] = colorcheck;
		
		for(int i : a[x]) {
			if (color[i] == colorcheck) {

                ok = false;
                return;
            }

			if(check[i] == false) {
				dfs(i, a,-colorcheck);
			}
		}
	}
}

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

문제

문제

출처

ICPC

[java] 게시판의 많은 반례를 확인했지만 왜 틀린지 모르겠습니다 ㅠ

noble5712 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말