글 읽기 - 1707 이분 그래프 질문입니다.

junh126 5년 전 0

어디가 틀린지 잘 모르겠습니다.

게시글에 있는 주의사항(초기화 등)도 확인했고, 반례도 돌려봤는데 잘 됐어요..

BFS로 시도해봤습니다.. 반례나 틀린 부분 지적해 주세요. 부탁드립니다.

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

vector <vector <int> > vc(20001);
int color[20001];//0 접근 아직 안함 , 1,-1==> color
int V, E;

void bfs(int v , int c) {
	
	queue < pair<int, int> > qu;
	qu.push(make_pair(v, c));
	while (!qu.empty()) {
		int nowV = qu.front().first;//현재 노드
		int nowC = qu.front().second;// 현재 노드의 컬러
		if (color[nowV]) { //이미 방문한 노드면 pop
			qu.pop();
			continue;
		}
		color[nowV] = nowC; //현재노드 색깔지정
		for (int i = 0; i < vc[nowV].size(); i++) {
			int nextV = vc[nowV][i];
			if (color[nextV]) continue; //이미 방문한 노드면 push안함.
			qu.push(make_pair(nextV, nowC * (-1))); //다음 노드 push
		}
		qu.pop();
	}

}
bool check() {
	for (int i = 1; i <= V; i++) {
		for (int j = 0; j < vc[i].size(); i++) {
			int tmp = vc[i][j];
			if (color[i] == color[tmp]) {
				return false;
			}
		}
	}
	return true;
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		memset(color, 0, sizeof(color));
		for (int i = 0; i < 20001; i++) vc[i].clear();
		cin >> V >> E;
		for (int i = 0; i < E; i++) {
			int tmp1,tmp2;
			scanf("%d %d", &tmp1, &tmp2);
			vc[tmp1].push_back(tmp2);
			vc[tmp2].push_back(tmp1);
		}
		int cnt = 0;
		for (int i = 1; i <= V; i++) {
			if (!color[i]) {
				bfs(i, 1);
			}
		}
		if (check()) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}

	}

	return 0;
}

djm03178 5년 전 1

34번째 줄의 i++을 j++로 바꾸면 통과됩니다.

junh126 5년 전 0

세상에나...

정말 감사합니다!

저게 안 보여서 한 두어시간 헤맨 것 같네요..

감사합니다!!!

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

문제

문제

출처

ICPC

1707 이분 그래프 질문입니다.

junh126 5년 전 0

djm03178 5년 전 1

junh126 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말