글 읽기 - 1707번 시간 초과 질문드립니다.

channuu 4년 전 0

왜 시간초과가 뜨는지 모르겠습니다ㅠㅠ

#include <stdio.h>
#define SIZE 20001

struct node
{
	int data;
	node* next;
};

node buf[200001];
node table[SIZE];
int bufcnt = 0;
int arr_col[SIZE];
bool check[SIZE];

node* myalloc(int data)
{
	buf[bufcnt].data = data;
	return &buf[bufcnt++];
}

void addNode(int curr, int data)
{
	node* newNode = myalloc(data);
	newNode->next = table[curr].next;
	table[curr].next = newNode;
}

bool dfs(int curr, int color)
{
	int rev_color = 3 - color;
	node* p = table[curr].next;
	//printf("%d %d\n", curr, color);
	while (p != NULL)
	{
		if (!check[p->data])
		{
			arr_col[p->data] = rev_color;
			check[p->data] = true;
			if (!dfs(p->data, rev_color))
				return false;
		}

		else
		{
			if (arr_col[p->data] == color)
				return false;
		}

		p = p->next;
	}
	return true;
}

void init(int vertex)
{
	for (int i = 1; i <= vertex; i++)
	{
		table[i].next = 0;
		arr_col[i] = 0;
		check[i] = false;
	}
	bufcnt = 0;
}

int main()
{
	int tc;
	scanf("%d", &tc);
	for(int testcase = 1; testcase <= tc; testcase++)
	{
		bool flag = true;
		int c, v;
		int start, end;
		scanf("%d %d", &c, &v);

		for (int j = 0; j < v; j++)
		{
			scanf("%d %d", &start, &end);
			addNode(start, end);
			addNode(end, start);
		}
		
		for (int i = 1; i <= c; i++)
		{
			if (!check[i])
			{
				check[i] = true;
				arr_col[i] = 1;
				if (!dfs(i, 1))
				{
					flag = false;
					break;
				}
			}
		}

		if (flag)
		{
			printf("YES\n");
		}
		else
			printf("NO\n");

		init(c);
	}

	return 0;
}

djm03178 4년 전 0

간선의 수가 20만개인데 양방향으로 만들고 있으니 총 40만개의 간선이 만들어집니다. 그런데 buf의 크기는 20만밖에 안 됩니다.

channuu 4년 전 0

아 기본적인걸 놓쳤네요ㅠㅠ 감사합니다!!

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

문제

문제

출처

ICPC

1707번 시간 초과 질문드립니다.

channuu 4년 전 0

djm03178 4년 전 0

channuu 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말