글 읽기 - 메모리초과

dlgpdus1117 3년 전 0

메모리 초과가 나왔는데

방문한곳을 체크했는데 메모리초과가 납니다.

어떤 문제가 발생한걸까요.

#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
bool check[1000*1000];
vector <int> g[1000*1000];
queue <int> q;

void dfs(int x) {
	if (check[x]) return;
	cout << x  <<" ";
	check[x] = true;

	for (int i = 0; i < g[x].size(); i++) {
		int y = g[x][i];
		dfs(y);
	}
}
void bfs(int x) {	
	check[x] = true;
	q.push(x);
	while (!q.empty()){
		x = q.front();
		for (int i = 0;i < g[x].size(); i++) {
			if (check[g[x][i]]) continue;
			check[g[x][i]] = true;
			q.push(g[x][i]);
		}
		cout <<q.front()<<" ";
		q.pop();
	 } 
}

int main() {
	int n, m, v;
	int input1, input2;

	cin >> n; //정점의 개수
	cin >> m; //간선의 개수
	cin >> v; //탐색 시작할 번호
	
	for (int i = 0; i <= n; i++) 
		check[i] = false;


	for (int i = 0; i < m; i++) {
		cin >> input1;
		cin >> input2;
		g[input1].push_back(input2);
		g[input2].push_back(input1);
	}

	for (int i = 0; i < n; i++) {
		vector <int> ex;
		ex = g[i];
		sort(ex.begin(), ex.end());
		g[i].clear();
		g[i] = ex;
	}
	
	dfs(1);
	cout << endl;
	for (int i = 0; i <= n; i++)
		check[i] = false;
	bfs(1);
	return 0;
}

klimmek55 3년 전 0

g가 vector<int> 1000*1000개짜리네요

1001정도로 하면 될 것 같습니다

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

문제

문제

출처

ICPC

메모리초과

dlgpdus1117 3년 전 0

klimmek55 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말