글 읽기 - bfs로 풀고싶습니다...

gksrlfw 4년 전 0

bfs 구현에서 어느부분이 틀린건지 가르쳐주세요...

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> a[1001];
int check[1001];

void bfs(int start, int c) {
	queue<int> q;
	check[start] = c;
	q.push(start);
	while (!q.empty()) {
		int node = q.front();
		q.pop();
		for (int i = 0; i < a[node].size(); i++) {
			int next = a[node][i];
			if (check[next] == 0) {
				check[next] = 3 - c;
				q.push(next);
			}
		}
	}
}
int main() {
	int t;
	cin >> t;
	while (t--) {
		int v, e;
		cin >> v >> e;
		memset(check, 0, sizeof(check));
		for (int i = 0; i < e; i++) {
			int n, m;
			cin >> n >> m;
			a[n].push_back(m);
			a[m].push_back(n);
		}
		for (int i = 1; i <= v; i++) {
			if (check[i] == 0) {
				bfs(i, 1);
			}
		}
		bool ok = true;
		for (int i = 1; i <= v; i++) {
			for (int j = 0; j < a[i].size(); j++) {
				int k = a[i][j];
				if (check[i] == check[k])
					ok = false;
			}
		}
		printf("%s", ok ? "YES" : "NO");
	}
}

hjm7091 4년 전 1

check[next] = 3 - c;

=> check[next] = check[node] * -1;

저도 같은 문제로 고민했는데

이런식으로 바꾸면 될 것 같아요.

gksrlfw 4년 전 0

감사합니다...

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

문제

문제

출처

ICPC

bfs로 풀고싶습니다...

gksrlfw 4년 전 0

hjm7091 4년 전 1

gksrlfw 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말