글 읽기 - [c언어] 출력초과?

kdr06006 4년 전 0

나름대로 잘 짠다고 짜봤는데 출력초과가 뜨는군요

잘 모르겠어서 질문드립니다.

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define _size 100001

int* link[_size], size[_size], cap[_size];
bool finished[_size];
int stack[_size], top = -1, dfsn[_size], cnt;
int Result[_size], result_idx, vertext[_size];

inline int min(int a, int b) { return a < b ? a : b; }

void re(int idx, int next)
{
	if (++size[idx] >= cap[idx]) {
		int* temp = (int*)realloc(link[idx], sizeof(int) * (cap[idx] += 10));
		link[idx] = temp;
	}
	link[idx][size[idx] - 1] = next;
}

void push(int a) { stack[++top] = a; }
int pop() { return stack[top--]; }

int DFS(int cur)
{
	dfsn[cur] = ++cnt;
	push(cur);

	int result = dfsn[cur];
	for (int i = 0; i < size[cur]; i++) {
		int next = link[cur][i];
		if (dfsn[next] == 0) result = min(result, DFS(next));
		else if (!finished[next]) result = min(result, dfsn[next]);
	}

	if (result == dfsn[cur]) {
		while (1) {
			int t = pop();
			Result[result_idx]++;
			finished[t] = true;
			vertext[t] = result_idx;

			if (t == cur) break;
		}

		result_idx++;
	}

	return result;
}

int main(void)
{
	for (int i = 0; i < _size; i++) link[i] = (int*)malloc(sizeof(int));

	int T;
	scanf("%d", &T);
	while (T--) {
		memset(size, 0, sizeof(size));
		memset(finished, 0, sizeof(finished));
		memset(dfsn, 0, sizeof(dfsn));
		memset(Result, 0, sizeof(Result));
		memset(vertext, 0, sizeof(vertext));
		top = -1; cnt = 0, result_idx = 0;

		int V, E, n1, n2;
		scanf("%d %d", &V, &E);
		while (E--) {
			scanf("%d %d", &n1, &n2);
			re(n1, n2);
		}

		for (int i = 0; i < V; i++) {
			if (dfsn[i] == 0) DFS(i);
		}

		bool flag = true;
		for (int i = 0; i < V; i++) {
			if (Result[vertext[i]] > 1) {
				printf("%d\n", i); 
				flag = false;
			}
		}

		if (flag) puts("Confused");
		puts("");
	}

	for (int i = 0; i < _size; i++) free(link[i]);
}

nahwasa 4년 전 3

반례입니다.

0이 떠야하는데 Confused가 뜨니

출력량이 예상보다 2배이상이라 출력초과가 뜨게됩니다.

출력초과도 틀렸습니다와 동일하다고 보심 됩니다!

1
1 1
0 0
답 : 0
출력 : Confused

kdr06006 4년 전 1

감사합니다!!

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

문제

문제

출처

ICPC

[c언어] 출력초과?

kdr06006 4년 전 0

nahwasa 4년 전 3

kdr06006 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말