글 읽기 - 거의 20번 제출했는데 안되네요...

qkrtjdrb9573 7년 전 1

20퍼센트 까진 돌아가다 틀린다고 나옵니다 ㅠ 질문에 나오는 테스트 케이스는 다돌렷는데 자꾸 틀리네요 ㅠ 코드 한번 봐주시면 감사하겠습니다!!

#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
#include<cstdio>
#include<algorithm>
#define MAX_V 20010

using namespace std;

typedef struct ss {
	int vertex;
	int stage;
}ss;

vector<vector<int > > v(MAX_V);
int check[MAX_V], K, V, E, No = 0, Yes = 0;
ss tmp;
queue<ss> q;

void bfs() {

	q.push(tmp);

	while (!q.empty()) {

		//divide stage into even number and odd number
		int here = q.front().vertex;
		int stage = q.front().stage;	

		q.pop();

		for (unsigned int i = 0; i < v[here].size(); i++) {
			int there = v[here][i];

			//find where we can go
			if (check[there] == 0) {
				check[there] = stage + 1;

				tmp.vertex = there;
				tmp.stage = stage + 1;

				q.push(tmp);
			}
			
			//find where we visited
			else {

				//'No' means whether you print 'NO' or not
				if ((check[here] % 2 == check[there] % 2) && No == 0) {

					printf("NO\n");
					No = 1;

					//initialize queue
					while (!q.empty()) q.pop();
			
					return;
				}
			}		
		}
		if (q.size() == 0 && stage == 1 && No == 0) {

			printf("NO\n");
			No = 1;

			//initialize queue
			while (!q.empty()) q.pop();
			
			return;
		}
	}

	//check where you do not visited
	for(int i=1; i<=V; i++) 

		//bfs
		if (check[i] == 0) {
			check[i] = 1;

			tmp.vertex = i;
			tmp.stage = 1;
			
			bfs();
		}

	//'Yes' means whether you print 'YES' or not
	if (No == 0 && Yes == 0) {
		Yes = 1;
		printf("YES\n");
	}
}

int main() {

	cin >> K;

	while (K--) {
		cin >> V >> E;

		//input data
		for (int i = 0; i < E; i++) {
			int x, y;
			cin >> x >> y;

			v[x].push_back(y);
			v[y].push_back(x);

		}
		
		//memory setting
		memset(check, 0, sizeof(check));

		//initialize varieties
		No = 0; Yes = 0; check[1] = 1;

		//starting point
		tmp.vertex = 1;
		tmp.stage = 1;

		bfs();

		//initialize vector and queue
		for (int i = 1; i <= V; i++) while (!v[i].empty()) v[i].pop_back();	
		while (!q.empty()) q.pop();
		
	}
}

etaehyun4 7년 전 1

3 1

1 2

가 반례일 것 같네요

qkrtjdrb9573 7년 전 0

답변 감사합니다!

근데 올려주신 케이스로 출력하면 NO 가 출력되는게 맞지 않나요?

1과 2는 연결되어있으니 이분 그래프지만 3은 연결이 되어있지 않으니 결과적으로는 아닌 게 되는 거 아닌가요?

etaehyun4 7년 전 2

이분 그래프의 정의에서는 Edge들 기준으로만 판단을 합니다.

그룹을 {1, 3} / {2} 로 나눴다고 생각했을 때 같은 그룹내에 인접한 노드들은 없으므로 이분 그래프라고 할 수 있습니다

qkrtjdrb9573 7년 전 0

아 제가 이분 그래프의 정의를 잘 몰랐던거 같네요 그러면 하나만 더 질문 드릴게요!

5 2

1 2

2 3

이런 식으로 나누면 이것도 이분 그래프라 할 수 있나요?

qkrtjdrb9573 7년 전 1

제가 물은 답변에 제가 답을 찾았네요!

위의 케이스는 YES가 출력되야 되는 답이었네요

댓글 감사드려요!!

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

문제

문제

출처

ICPC

거의 20번 제출했는데 안되네요...

qkrtjdrb9573 7년 전 1

etaehyun4 7년 전 1

qkrtjdrb9573 7년 전 0

etaehyun4 7년 전 2

qkrtjdrb9573 7년 전 0

qkrtjdrb9573 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말