글 읽기 - 이분그래프 문제 질문..

workbase123 6년 전 0

이분그래프 문제를 풀고 VS에서도 testcase 잘 맞아서 제출했는데, 왜 틀릴까요

제가 캐치하지 못한 case가 어느 경우인지 궁금합니다...

20퍼 정도까지 돌아가다가 틀렸습니다가 나옵니다.

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int> > v;
vector<int> color;

bool isBipartite;
int numOfV, numOfE;

void dfs(int cur,int c) {
	color[cur] = c;
	for (size_t i = 0; i < v[cur].size(); ++i) {
		int next = v[cur][i];
		if (!color[next]) {
			dfs(next, 3 - c);
		}
	}
}

void examBipartite(void) {

	for (int i = 1; i <= numOfV; ++i) {
		for (size_t j = 0; j < v[i].size(); ++j) {
			int next = v[i][j];
			if (color[next] == color[i]) {
				isBipartite = false;
				return;
			}
		}
	}
}

int main(void) {
	int t;
	cin >> t;

	while (t--) {
		isBipartite = true;

		cin >> numOfV >> numOfE;

		v.resize(numOfV + 1);
		color.resize(numOfV + 1, 0);

		for (int i = 1; i <= numOfV; ++i) {
			v[i].clear();
		}
		
		for (int i = 0; i < numOfE; ++i) {
			int from, to;

			cin >> from >> to;

			v[from].push_back(to);
			v[to].push_back(from);
		}

		for (int i = 1; i <= numOfV; ++i) {
			if (!color[i]) dfs(i, 1);
		}

		examBipartite();

		if (isBipartite == true) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
	return 0;
}

cheetose 6년 전 0

color의 초기화가 잘못된 방식으로 진행되고 있습니다.

2
3 3
1 2
2 3
3 1
6 3
4 5
5 6
1 3

Output 
NO
YES

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

문제

문제

출처

ICPC

이분그래프 문제 질문..

workbase123 6년 전 0

cheetose 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말