글 읽기 - 20%에서 계속 틀립니다 ㅠㅠ

jupiny 6년 전 0

인접리스트와 BFS를 이용해서 풀었습니다.

답변들에 있는 모든 반례 케이스를 돌려봐도 잘 되는데 계속 20%에서 틀리는 이유가 무엇일까요?ㅠㅠ

반례를 찾아주시면 감사하겠습니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<int> > adj; // 인접리스트
vector<int> color; // -1은 아직 방문 X, 0 또는 1은 방문한 정점의 색

int check_color(int color_size) {
	for(int i=1; i<=color_size; i++)
		if(color[i] == -1)
			return i;
	return -1;
}

int main() {
	int k;
	int v, e;
	int a, b;
	cin >> k;

	for(int t=0; t<k; t++) {
		cin >> v >> e;
		adj.resize(v+1);
		color.resize(v+1, -1);

		// 인접리스트 저장
		for(int i=0; i<e; i++) {
			cin >> a >> b;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}

		bool check = true;
		while(true) {

			// 모든 정점을 방문하였거나 인접하면서 같은 색의 정점을 발견한 경우 종료
			int not_visit = check_color(v);
			if(not_visit == -1 || !check)
				break;

			queue<int> q;
			q.push(not_visit);
			color[not_visit] = 0;

			// BFS 시작
			while(!q.empty()) {
				int cur = q.front();
				int cur_color = color[cur];
				int next_color = (cur_color + 1) % 2;
				int cur_size = adj[cur].size();
				q.pop();
				for(int j=0; j<cur_size; j++) {
					int next = adj[cur][j];

					// 인접하면서 같은 색인 정점
					if(color[next] == cur_color) {
						check= false;
						break;
					}

					// 아직 방문하지 않은 정점
					if(color[next] == -1) {
						q.push(next);
						color[next] = next_color;
					}
				}
				if(!check)
					break;
			}
		}

        // 같은 색의 정점을 발견한 적 없이 모든 정점을 방문한 경우
		if(check)
			cout << "YES" << endl;

		// 같은 색의 정점을 발견해서 종료한 경우
		else
			cout << "NO" << endl;
	}

	return 0;
}

djm03178 6년 전 1

테케마다 초기화가 제대로 안 되는 듯합니다.

3 3

1 2

2 3

3 1 // NO

3 3

1 2

2 3

3 1 // YES

똑같은 케이스를 두 번 넣었는데 결과가 다르게 나왔습니다.

jupiny 6년 전 0

와 대박

감사합니다 ㅠㅠ

vector를 resize하기 전에 clear() 함수로 초기화했더니 바로 해결됐네요ㅎㅎㅎ

resize를 하더라도 그 전에 clear() 함수로 초기화를 해야되군요! resize의 의미 안에 초기화도 포함되있는 줄 알았습니다 ㅠㅠ

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

문제

문제

출처

ICPC

20%에서 계속 틀립니다 ㅠㅠ

jupiny 6년 전 0

djm03178 6년 전 1

jupiny 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말