글 읽기 - 반례를 도저히 못찾겠습니다...

abdbscd2 5년 전 0

반례 찾아주시면 정말 감사하겠습니다.

젤 밑에 있는 함수 3개가 메인코드 입니다.

(나머지는 그래프 위한 배경코드..)

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

#define TRUE 1
#define FALSE 0
#define MAX_LEN 20001

typedef struct _node
{
	int Data;
	struct _node * Next;
} Node;

typedef struct _list
{
	int numOfData;
	Node * head;
}List;

void ListInit(List *plist)
{
	plist->numOfData = 0;
	plist->head = (Node *)malloc(sizeof(Node));
	plist->head->Next = NULL;
}

int LCount(List *plist)
{
	return plist->numOfData;
}

void LInsert(List *plist, int data)
{
	Node *newNode = (Node *)malloc(sizeof(Node));
	newNode->Data = data;
	newNode->Next = plist->head->Next;
	plist->head->Next = newNode;
	plist->numOfData++;
}

typedef struct _graph
{
	int nv;
	int ne;
	List * adjList;
} Graph;

void GraphInit(Graph *pg, int nv)
{
	pg->ne = 0;
	pg->nv = nv;
	pg->adjList = (Node *)malloc(sizeof(Node)*(nv + 1));

	for (int i = 0; i <= nv; i++)
		ListInit(&(pg->adjList[i]));
}

void GraphDestroy(Graph *pg)
{
	if (pg->adjList != NULL)
		free(pg->adjList);
}

void AddEdge(Graph *pg, int fromV, int toV)
{
	LInsert(&(pg->adjList[fromV]), toV);
	LInsert(&(pg->adjList[toV]), fromV);
	pg->ne++;
}

void DFS(Graph * pg, int x, int number);
void CheckGraph(Graph *pg, int x, int number);

int Check[MAX_LEN] = { 0 };
int numOfComp = 0;
int count=0;
int V, E;

int main()
{
	int fromV, toV;
	Graph graph;
	int test_case;
	
	scanf("%d", &test_case);
	for (int test = 0; test < test_case; test++)
	{
		count = 0;
		scanf("%d %d", &V, &E);
		GraphInit(&graph, V);


		for (int i = 0; i < E; i++)
		{
			scanf("%d %d", &fromV, &toV);
			AddEdge(&graph, fromV, toV);
		}

		DFS(&graph, fromV, 1);
		CheckGraph(&graph, fromV, Check[fromV]);

		if (count != -1)
			printf("YES\n");

		for (int i = 1; i <= V; i++)
			Check[i] = 0;

		GraphDestroy(&graph);
	}

	return 0;
}

void CheckGraph(Graph *pg, int x, int number)
{

	int size = LCount(&(pg->adjList[x]));
	Node * tempNode = pg->adjList[x].head;
	for (int i = 0; i < size; i++)
	{
		tempNode = tempNode->Next;
		int temp = tempNode->Data;
		if (Check[temp] == 3 - number)
		{
			Check[temp] = 0;
			CheckGraph(pg, temp, 3 - number);
		}
		else if (Check[temp] == 0)
		{
			continue;
		}
		else
		{
			count = -1;
			printf("NO\n");
			return;
		}

	}

}

void DFS(Graph * pg, int x, int number)
{
	Check[x] = number;
	int size = LCount(&(pg->adjList[x]));
	Node * tempNode = pg->adjList[x].head;
	for (int i = 0; i < size; i++)
	{
		tempNode = tempNode->Next;
		int temp = tempNode->Data;
		if (Check[temp] == 0)
		{
			DFS(pg, temp, 3-number);
		}
	}

}

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

문제

문제

출처

ICPC

반례를 도저히 못찾겠습니다...

abdbscd2 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말