글 읽기 - 이분 그래프 예외케이스 궁금합니다

jae159 2년 전 0

떨어진 정점 케이스도 생각도 했는데 도저히 안나오네요

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;





#define VERTEX_NUM 20001
vector<int> link[VERTEX_NUM];
int color[VERTEX_NUM];
int n, m;
bool changeColor = false;


void InsertColorBFS(int num)
{
	bool Same;

		if (!changeColor) //빨간색
		{
			color[num] = 1;
		}
		else {			//파란색
			color[num] = -1;
		}



	Same = true; //여러개로 연결된 노드들이 다른색 안되도록 

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

	
		if (color[next] == 0)
		{			
			if (Same) //여러개로 연결된 노드들을 하나의 색으로 합치기 위해
			{
				changeColor = !changeColor;
				Same = false;
			}

			InsertColorBFS(next);
		}
	}
}

bool ColorCheckBFS()
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < link[i].size(); j++)
		{
			int next = link[i][j];
			if (color[i] == color[next])
			{
				return false;
			}
		}
	}

	return true;
}

void Solution()
{
	int result = 0;
	int caseNum;

	cin >> caseNum;


	for (int i = 0; i < caseNum; i++)
	{
		memset(color, 0, sizeof(color));
		for (int i = 0; i < VERTEX_NUM; i++)
		{
			link[i].clear();
		}

		cin >> n >> m;

		for (int i = 0; i < m; i++)
		{
			int u, v;
			cin >> u >> v;
			link[u].push_back(v);
			link[v].push_back(u);
		}

		for (int j = 1; j <= n; j++)
		{
			if (color[j] == 0) {
				InsertColorBFS(j);
			}

			changeColor = false;
		}

		if (ColorCheckBFS())
		{
			cout << "YES" << '\n';
		}
		else
		{
			cout << "NO" << '\n';
		}

		changeColor = false;
	}

}

int main()
{
	Solution();

}

cchccc 2년 전 1

입력

1
4 3
1 2
2 3
1 4

출력

답

YES

반례입니다

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

문제

문제

출처

ICPC

이분 그래프 예외케이스 궁금합니다

jae159 2년 전 0

cchccc 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말