글 읽기 - 어디가 틀렸는지 모르겠습니다. 도와주세요!

captureit 5년 전 0

고민고민하다가 도저히 해결이 안되서 질문을 드립니다.

반복문으로 색깔이 부여되지 않은 점을 찾아 해당 점으로부터 BFS를 수행해서 색이 부여되지 않은 인접한 점에 반대되는 색을 부여되도록하고,

마지막에 모든 노드들에 대하여 서로 인접한 점이 자신과 같은 색을 가지면 이분 그래프가 생성되지 않다고 판단하는 것을 코드로 구현하였는데

계속 틀렸다고 나옵니다.. 이유가 뭘까요? 부탁드립니다..

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
enum { RED = 1, BLUE = -1, INITIAL = 0 };
using namespace std;

int numberOfCase, numberOfEdge, numberOfVertex;
int color_arr[20001];
vector<int> graph[20001];

void bfs(int number, int color) {

	queue<pair<int, int>> q;
	q.push(pair<int, int>(number, color));

	if (color_arr[number] == 0)
		color_arr[number] = color;

	while (!q.empty()) {

		int number = q.front().first;
		int color = q.front().second;
		q.pop();

		for (int i = 0; i < (signed)graph[number].size(); i++) {

			int value = graph[number][i];

			if (color_arr[value] == 0) {
				color_arr[value] = color*-1;
				q.push(pair<int, int>(value, color*-1));
			}
		}
	}
}

bool isBipartite() {

	for (int i = 1; i <= numberOfVertax; i++) {

		for (int j = 0; j < (signed)graph[i].size(); i++) {

			int value = graph[i][j];

			if (color_arr[i] == color_arr[value]) {
				return false;
			}
		}
	}

	return true;
}

int main() {

	memset(color_arr, INITIAL, sizeof(color_arr));

	cin >> numberOfCase;

	for (int i = 0; i < numberOfCase; i++)
	{
		cin >> numberOfVertex >> numberOfEdge;
		for (int j = 0; j < numberOfEdge; j++) {

			int start, end;
			cin >> start >> end;
			graph[start].push_back(end);
			graph[end].push_back(start);
		}

		for (int i = 1; i <= numberOfVertex; i++) 
			if (color_arr[i] == INITIAL)
				bfs(i, RED);

		if (isBipartite()) 
			printf("YES\n");
		else    
			printf("NO\n");

		for (int i = 1; i <= numberOfVertex; i++)
			graph[i].clear();

		memset(color_arr,INITIAL, sizeof(color_arr));
	}

	return 0;
}

djm03178 5년 전 1

질문을 올릴 때는 틀렸던 코드를 반드시 한 자도 다름없이 그대로 올려주세요. 이 코드는 아예 컴파일 에러가 나고, 컴파일 에러가 나는 곳을 고쳐도 틀렸습니다가 아니라 런타임 에러가 납니다. 그리고 그 둘만 고치면 정답을 받습니다.

40번째 줄: numberOfVertax - > numberOfVertex

42번째 줄: i++ -> j++

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

문제

문제

출처

ICPC

어디가 틀렸는지 모르겠습니다. 도와주세요!

captureit 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말