글 읽기 - 반례를 찾고싶습니다.

jumpingz 7년 전 0

예제는 물론이고.. 이것저것 데이터를 생각해서 넣어봣는데.. 요 한가지 경우가 조금 애메해서 처리는 해보았으나 역시 틀렷다고하더군요..

일단

6 4

1 2

2 4

4 5

5 6

위 데이터도 YES 가 나오는게 맞는지요??

맞다면 아래코드에서 어느부분이 틀렷는지 봐주시면 감사하겟습니다.

#include <cstdio>
#include <vector>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;

int C = 0, check[20001];
vector<vector<int> > V(20001);

void DFS(int v, int color);

int main()
{
	int i, j, k, a, b, N, M, T, flag;

	scanf("%d", &T);

	for (j = 0; j < T; j++)
	{
		flag = 0;
		scanf("%d%d", &N, &M);

		for (i = 0; i < M; i++)
		{
			scanf("%d%d", &a, &b);
			V[a].push_back(b);
			V[b].push_back(a);
		}

		for (i = 1; i <= N; i++)
			DFS(i, 1);
		
		for (i = 1; i <= N; i++)
		{
			for (k = 0; k < V[i].size(); k++)
			{
				if (check[i] == check[V[i][k]])
				{
					flag = 1;
					break;
				}
			}

			if (flag == 1)
				break;
		}
		
		if(flag == 1)
			printf("NO\n");
		else
			printf("YES\n");
        
        for(i = 1; i <= N; i++)
            check[i] = 0;
	}

	return 0;
}


void DFS(int v, int color)
{
	if (check[v] == 1 || check[v] == 2)
		return ;

	if (color == 1)
	{
		check[v] = 2;
		color = 2;
	}
	else
	{
		check[v] = 1;
		color = 1;
	}

	for (int i = 0; i < V[v].size(); i++)
	{
		if (check[V[v][i]] == 0)
			DFS(V[v][i], color);
	}
}

skykhs3 7년 전 1

한 테스트 케이스 끝날때마다 벡터 V 초기화 안하셔서 틀린것 같습니다.

jumpingz 7년 전 0

아이고... 가장 기초적인걸 안했군요 ㅋㅋㅋ 덕분에 맞췄습니다. 감사합니다 ㅎ

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

문제

문제

출처

ICPC

반례를 찾고싶습니다.

jumpingz 7년 전 0

skykhs3 7년 전 1

jumpingz 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말