글 읽기 - 주석有) FAQ 확인하고 반례도 다 확인했는데 무엇이 틀린지 아리송합니다.

kangsy763 4년 전 0

일단 각 점에 1또는 0을 할당하여 뺀 값의 절대값이 1인지 0인지로 판단하여서 풀었습니다.

vector 배열을 만들면서 초기화하고 싶은데 방법을 잘 모르겠습니다. . .

vector<int> vec(200,0); 이렇게 만들면 vec[?] 이 값이 다 0이 되고 저 값을 변경이 안되더라구요..

그리고 for문 안에 vector의 size를 조건으로 두었을 때에 컴파일에러가 나서 따로 int 형을 선언해서 그곳에 집어넣었습니다. 아마 여기서 자동형변환이 되는거겠죠 ? ? 더 좋은 방법도 알고 싶습니다.

반례 다 들어맞는 것 같은데 무엇이 문제인지 알고 싶습니다.

#include <cstdio>
#include <cstring>
#include <vector>
#include <cstdlib>
#include <queue>
#include <utility>
using namespace std;
int k, v, e;
vector<int> vec[20000];				//e의 정보를 넣기위함입니다.
vector<pair<int, int> >vp;			//이후에 color 들을 체크하기 위함입니다.
queue<int> q;
int visit[20000];
int color[20000];
int clr = 1;						//색 정보입니다. 0,1 2개로 나뉘어져 있습니다.
void bfs(int start) {
	q.push(start);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		int sz = vec[x].size();
		for (int i = 0; i < sz; i++) {
			if (visit[vec[x][i]] == 0) {		//시작점으로부터 i점 방문한 적이 없고,
				if (vec[x][i] > 0 && vec[x][i] <= 200000) {		//그것이 x 와 i가 이어져 있으면, 이 부분은 vec 선언하면서 0초기화 하고싶은데 방법을 모르겠습니다 ㅜㅜ
					q.push(vec[x][i]);
					visit[vec[x][i]] = 1;
					color[vec[x][i]] = clr;
					if (clr) clr = 0;
					else clr = 1;
				}
			}
		}
	}
}
int main() {
	int check = 1;
	scanf("%d", &k);
	while (k--) {
		scanf("%d %d", &v, &e);
		for (int i = 0; i < e; i++) {
			int a, b;
			scanf("%d %d", &a, &b);
			vec[a - 1].push_back(b - 1);
			vec[b - 1].push_back(a - 1);
			vp.push_back(make_pair(a - 1, b - 1));		//어느 점과 어느점이 이어져있는지에 대한 정보를 넣었습니다.
		}
		for (int i = 0; i < v; i++) {
			if (vec[i].size() && visit[i] == 0) {		//만약 연결이 되어있고 그 점을 방문하지 않았다면
				visit[i] = 1;							//방문 처리
				color[i] = clr;							//색을 넣고
				if (clr) clr = 0;						//그 다음을 위해 색을 변경시킵니다.
				else clr = 1;
				bfs(i);									//그 점으로부터 탐색을 시작합니다.
			}
		}
		int vpsize = vp.size();						//for 문 안에 바로 vp.size()를 넣으면 컴파일에러가 일어나서 이렇게 표현했는데 좋은방법 없을까요?
		for (int i = 0; i < vpsize; i++) {
			if (abs(color[vp[i].first] - color[vp[i].second])) check = 1;		//vp를 이용해 color 배열에 접근하여서 그 값들을 뺀 절대값이 1이면 check를 그대로 1
			else { check = 0; break; }											//만약 아니라면 이분 그래프가 아니므로 0 으로 바꾸고 break
		}
		if (check) printf("YES\n");
		else printf("NO\n");

		vec->clear();
		vp.clear();
		memset(color, 0, sizeof(color));
		memset(visit, 0, sizeof(visit));
	}
	return 0;
}

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

문제

문제

출처

ICPC

주석有) FAQ 확인하고 반례도 다 확인했는데 무엇이 틀린지 아리송합니다.

kangsy763 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말