글 읽기 - 게시판에 있는 반례들 모두 맞게 나오는데 틀렸다고 하네요ㅠㅠ

kij0621 4년 전 0

다른 반례 알려주시면 감사하겠습니다ㅠㅠ!!

#include<stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int K, V, E; // 테스트 케이스, 정점, 간선


string bfs(vector<vector<int>> &element, int color[], int start){
	//printf("%d ", start);
	string result = "YES";
	queue<int> q;
	q.push(start);
	color[start] = 1;

	while(!q.empty()){
		int a = q.front();
		q.pop();

		for(int i=0; i<element[a].size(); i++){
			if(color[element[a][i]] == 0){ //아직 색 바뀐적 없으면 인접했으니까 색 바꾸기
				if(color[a] == 1){
					color[element[a][i]] = 2;
				}else if(color[a] == 2){
					color[element[a][i]] = 1;
				}

				q.push(element[a][i]);
				//printf("%d ", element[a][i]);


			}else { // 색 바뀐 적 있고
				if(color[a] == color[element[a][i]]){ // 같은 색이라면 이분 그래프 아님
					result = "NO";
					break;
				}
			}
		}

	}

	return result;
}

int main(){
	scanf("%d", &K);
	int start = 0;

	for(int i=0; i<K; i++){
	scanf("%d %d", &V, &E);

	vector<vector<int>> element(20001);
	int color[20001] = {0,};
	
		for(int j=0; j<E; j++){ //그래프 만들기
			int x, y;
			scanf("%d %d", &x,&y); // x, y는 인접 노드
			if(j==0){
				start = x;
			}
			element[x].push_back(y);
			element[y].push_back(x);
		}

		string result = bfs(element, color, start);
		for(int d=1; d<=V; d++){
			if(color[d] == 0){ // 아직 방문하지 않은 노드가 있으면 다시 bfs
				result = bfs(element, color, d);
			}
		}
		cout << result << '\n';

	}

}

djm03178 4년 전 1

한 번 탐색해서 답이 NO로 결정났으면 이후 답을 다시 YES로 바꿀 일은 절대로 없습니다.

kij0621 4년 전 0

72라인을

if(color[d] == 0 && result == "YES")로 수정했더니

맞았다고 나오네요ㅠㅠ

djm03178님 어제부터 정말 감사합니다!!!

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

문제

문제

출처

ICPC

게시판에 있는 반례들 모두 맞게 나오는데 틀렸다고 하네요ㅠㅠ

kij0621 4년 전 0

djm03178 4년 전 1

kij0621 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말