글 읽기 - 안되는 반례를 못찾겠습

dibgh 6년 전 0

저 말고도 질문해주신 분들의 예제를 다 넣어봤는데 제대로 나옵니다 근데 자꾸 틀렸다고 나오네요

제가 생각 못한 반례가 더 있는 건가요?

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
#include<string>

using namespace std;

vector<int> a[20001];
int check[20001];


string bfs(int start,int count)
{
	queue<int> q;
	q.push(start);
	check[start] = count;

	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		int size = a[x].size();
		for (int i = 0; i < size; i++)
		{
			int next = a[x][i];
			if (check[next] == 0 && count ==1)
			{
				count = 2;
				check[next] = count;
				q.push(next);
			}
			else if (check[next] == 0 && count == 2)
			{
				count = 1;
				check[next] = count;
				q.push(next);
			}
			else if (check[next] ==check[x])
			{
				return "NO";
			}
		}
	}
	return "YES";
}

int main()
{
	int ncase;
	int n, m;
	int u, v;
	int start;
	int size = 0;
	vector<string> str;

	scanf("%d", &ncase);

	for (int i = 0; i < ncase; i++)
	{
		scanf("%d %d", &n, &m);
		for (int j = 0; j <m; j++)
		{
			scanf("%d %d", &u, &v);
			a[u].push_back(v);
			a[v].push_back(u);
			if (j == 0)
			{
				start = u;
			}
		}
		str.push_back(bfs(start, 1));
		memset(check, 0, sizeof(check));
		for (int k = 1; k <=n; k++)
		{
			a[k].clear();
		}
	}
	size = str.size();
	for (int i = 0; i < size; i++)
	{
		cout << str[i] <<'\n';
	}
}

djm03178 6년 전 0

5 4

1 2

3 4

4 5

5 3

100 4

1 100

10 20

20 30

30 10

이 경우 둘 다 NO가 나와야 하는데 둘 다 YES가 나옵니다.

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

문제

문제

출처

ICPC

안되는 반례를 못찾겠습

dibgh 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말