글 읽기 - 메모리 초과 질문

QuqqU 6년 전 0

처음에 생각없이 플로이드로 풀었다가 런타임에러가 나서 bfs로 고쳤는데요,

왜 메모리 초과가 나죠...?

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

queue<int> q;
vector<int> edge[10005], v;
vector<bool> discovered(10005, false);

int main() {
	int n, m; scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		int a, b; scanf("%d %d", &a, &b);
		edge[b].push_back(a);
	}

	int ans = -1;
	for (int i = 1; i <= n; i++) {
		int rlt = 0;
		q.push(i);
		fill(discovered.begin(), discovered.end(), false);
		
		while (!q.empty()) {
			int curr = q.front();
			q.pop();
			for (int next : edge[curr]) {
				if (!discovered[next])
					rlt++; q.push(next);
			}
		}

		ans = max(ans, rlt);
		v.push_back(rlt);
	}

	for (int i = 1; i <= n; i++)
		if (v[i - 1] == ans) printf("%d ", i);



	return 0;
}

hun222y 6년 전 1

bfs 돌면서 큐가 터지게 됩니당

왜냐 ...

if (!discovered[next])
rlt++; q.push(next);

여기에서 ..... discovered[next] = true;를 안해주었기 떄문이겠죠? ㅎㅎ

QuqqU 6년 전 0

아.../!!!! 그렇네요!!! 감사합니다!!!

+ discovered[next] = true;했는데 출력초과가 뜨는데 이건 왜 그런건 가요??

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

문제

문제

출처

ICPC

메모리 초과 질문

QuqqU 6년 전 0

hun222y 6년 전 1

QuqqU 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말