글 읽기 - 반례 부탁드립니다..ㅠㅠ

cllollo 6년 전 0

60%에서 오답이라고 나오는데, 무엇이 잘못된지 잘 모르겠습니다.ㅠㅠ 반례나 힌트라도 주실수있나요 ㅠㅠ

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

int v, k, e;
int check[20001] = { 0, };
vector<vector<int>> arr;
vector<bool> visited;

void input()
{
	arr.clear();
    visited.clear();
	scanf("%d %d", &v, &e);
	
	arr = vector<vector<int>>(v + 1);
	visited = vector<bool>(v + 1, false);
	for (int i = 0; i < v; i++) check[i] = 0;
	
	for (int i = 0; i < e; i++)
	{
		int start, end;
		scanf("%d %d", &start, &end);
		arr[start-1].push_back(end-1);
		arr[end-1].push_back(start-1);
	}

	for (int i = 0; i < v; i++)
		sort(arr[i].begin(), arr[i].end());

	

}

int chooseTeam(int node)
{
	if (check[node] == 1) //A이면 
		return 2; //B값

	else //B이면
		return 1; //A값
}

void bfs(int node)
{
	queue<int> q;
	q.push(node);
	check[node] = 1;
	visited[node] = true;

	while (!q.empty())
	{
		int here = q.front();
		int team = chooseTeam(here);
		q.pop();

		for (int i = 0; i < arr[here].size(); i++)
		{
			int next = arr[here][i];

			if (check[next] == 0)
			{
				check[next] = team;
				q.push(next);
			}
			else
			{
				if (check[next] != team)
				{
					printf("NO\n");
					return;
				}
			}


		}
	}

	printf("YES\n");

}


int main()
{
	scanf("%d", &k);
	for (int i = 0; i < k; i++)
	{
		input();
   		bfs(1);
	}

	return 0;
}

djm03178 6년 전 0

힌트는 질문 게시판에 있습니다.

cllollo 6년 전 0

힌트를 보고 코드를 짯는데, 답이 나오질 않습니다.

djm03178 6년 전 0

1에서만 bfs를 하면 답이 안 나온다는 게 힌트입니다.

cllollo 6년 전 0

아아 정말 감사합니다.

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

문제

문제

출처

ICPC

반례 부탁드립니다..ㅠㅠ

cllollo 6년 전 0

djm03178 6년 전 0

cllollo 6년 전 0

djm03178 6년 전 0

cllollo 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말