글 읽기 - 어떤 반례가 있는지 모르겠네요 ㅠㅠ

aod0326 7년 전 0

BFS로 풀었는데 어디가 잘못됬는지 모르겠네요

질문 답변으로 올라온 예시들도 다 정답으로 나오는데 ㅠㅠ

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

public class Main{
	public static boolean bfs(ArrayList<Integer>[] gr, int b[], int start){
		Queue<Integer> q = new LinkedList<Integer>();
		if(b[start] == 0)
			b[start] = 1;
		int cur = start;
		q.add(cur);
		while(!q.isEmpty()){
			cur = q.remove();
			for(int y : gr[cur]){
				if(b[y] == 0){
					b[y] = 3-b[cur];
				}else if(b[y] == b[cur]){
					return false;
				}
			}
		}
		return true;
	}
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int T;
		int V,E;
		T = sc.nextInt();
		for(int i=0;i<T;i++){
			V = sc.nextInt();
			E = sc.nextInt();
			ArrayList<Integer>[] gr = (ArrayList<Integer>[]) new ArrayList[V+1];
			
			for(int j=1;j<=V;j++)
				gr[j] = new ArrayList<Integer>();
			
			for(int j=1;j<=E;j++){
				int from = sc.nextInt();
				int to = sc.nextInt();
				gr[from].add(to);
				gr[to].add(from);
			}
			
			for(int j=1;j<=V;j++)
				Collections.sort(gr[j]);
			int b[] = new int[V+1];
			Arrays.fill(b, 0);
			boolean tf;
			for(int j=1;j<=V;j++){
				tf = bfs(gr,b,j);
				if(tf == false){
					System.out.println("NO");
					break;
				}
				if(j == V)
					System.out.println("YES");
			}			
		}
		
	}
}

q.add(cur);
        while(!q.isEmpty()){
            cur = q.remove();
            for(int y : gr[cur]){
                if(b[y] == 0){
                    b[y] = 3-b[cur];
                }else if(b[y] == b[cur]){
                    return false;
                }
            }
        }

일단 여기 보시면 큐에 다음 정점들을 추가를 안 해서 BFS가 안 되고 있어요

aod0326 7년 전 0

아 거길 빼먹었구나.. 근데 결과는 왜 괜히 잘나와가지고 ㅋㅋ

감사합니다!! 허접한 실수를 해버렸네요 ㅎㅎ

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

문제

문제

출처

ICPC

어떤 반례가 있는지 모르겠네요 ㅠㅠ

aod0326 7년 전 0

codeonwort 7년 전 1

aod0326 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말