글 읽기 - 반례를 찾아주실 분 구합니다[쉽습니다]

kkw564 7년 전 0

몇시간째 이 코드에 대해 반례를 생각해보고 있지만 마땅히 생각나는 반례가 없네요

도와주세요 !

#include <iostream>
#include <cstdio>
#include <vector>
#include <memory.h>

using namespace std;

int color[1001];
int main()
{
	int tc;
	scanf("%d", &tc);

	while (tc--)
	{
		int n, m;
		scanf("%d %d", &n, &m);

		vector<vector<int>> vc(n + 1);
		memset(color, 0, sizeof(color));

		for (int i = 0; i < m; i++)
		{
			int from, to;
			scanf("%d %d", &from, &to);
			vc[from].push_back(to);
			vc[to].push_back(from);
		}

        // 정점 색칠
		for (int i = 1; i <= n; i++)
		{
			if (color[i] == 0)
				color[i] = 1;
			else
				continue;
			for (int j = 0; j < vc[i].size(); j++)
			{
				int here = vc[i][j];
				if (color[here] == 0)
					color[here] = 2;
			}
		}

        
        // 이웃한 정점이 같은 색인지 체크
		bool chk = true;
		int search;
		for (int i = 1; i <= n; i++)
		{
			if (color[i] == 1)
				search = 2;
			else
				search = 1;
			for (int j = 0; j < vc[i].size(); j++)
			{
				if (color[vc[i][j]] != search)
				{
					chk = false;
					break;
				}
			}
			if (!chk)
				break;
		}

		if (chk)
			printf("possible\n");
		else
			printf("impossible\n");
	}
	return 0;
}

jacob_1120 3년 전 0

제 코드도 보고 알려주세요

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

문제

문제

출처

ICPC

반례를 찾아주실 분 구합니다[쉽습니다]

kkw564 7년 전 0

jacob_1120 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말