글 읽기 - 반례 질문

mesh153 2년 전 1

BFS를 활용해서 작성해봤는데... 50%에서 틀렸다고 뜨네요.. 혹시 뭐가 문제인지 알수있을까요??.

인접노드를 Q에 넣어주기전에 문자가 서로 같으면 반복문을 탈출하여 NO를 출력하게 해주었습니다.

#pragma warning(disable:4996)

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>

#define MAX 20001

using namespace std;

int T, V, E;
vector<int> map[MAX];

char ch[MAX];
int isVisited[MAX];

void init(int V) {
	memset(isVisited, 0, sizeof(isVisited));
	memset(ch, 0, sizeof(ch));

	for (int i = 0; i <= V; i++)
		map[i].clear();
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> T;

	for (int i = 0; i < T; i++) {
		cin >> V >> E;
		init(V);

		for (int j = 0; j < E; j++) {
			int a, b;
			cin >> a >> b;
			map[a].push_back(b);
			map[b].push_back(a);
		}

		queue<int> q;
		q.push(1);
		ch[1] = 'O';
		int flag = false;

		while (!q.empty()) {
			int now = q.front();
			q.pop();
			if (isVisited[now] == 1) continue;
			isVisited[now] = 1;

			//인접 노드 O,X 판별-> 값이 바뀌면 그 그래프는 이분 그래프가 아니다?
			//인접 노드 값들을 Q에 넣어주기
			for (int j = 0; j < map[now].size(); j++) {
				int next = map[now][j];

				if (ch[now] == 'X') {
					if (ch[now] == ch[next] && ch[next] != 0) {
						flag = true;
						break;
					}
					ch[next] = 'O';
				}
				else {
					if (ch[now] == ch[next] && ch[next] != 0) { 
						flag = true;
						break;
					}
					ch[next] = 'X';
				}


				q.push(next);
			}

			if (flag) break;
		}
		if (flag) cout << "NO" << "\n";
		else cout << "YES" << "\n";
	}

	return 0;
}

mesh153 2년 전 7

5 4

1 2

3 4

3 5

4 5

이게 반례네요... 그래프가 완전히 연결되어 있다는 보장이 없으니 1~V까지 모든 노드를 탐색해줘야 됩니다. 여기서 시간초과 문제가 발생할 수 있으니 isVisited배열 하나 만들어서 체크 해주었습니다

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

문제

문제

출처

ICPC

반례 질문

mesh153 2년 전 1

mesh153 2년 전 7

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말