글 읽기 - BFS 메모리 초과 문제

luciferkala 4년 전 0

어떤 방식으로 해결해야 할 지 감이 잘 안옵니다.

아예 DFS로 풀어야 하나요?

#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;

int N,M;
vector<int> map[10001];
int x,y;
int ans[10001] = {0};
bool visited[10001] = {false};
int mx;
void BFS(int start) {
  queue<int> q;
  q.push(start);
  visited[start] = true;
  while(!q.empty()) {
    int now = q.front();
    q.pop();

    for(int i = 0; i < map[now].size(); i++) {
      if(visited[map[now][i]]) continue;
      visited[i] = true;
      q.push(map[now][i]);
    }
    ans[start]++;
  }
    if(mx < ans[start])
        mx = ans[start];
}

int main() {
  scanf("%d %d", &N, &M);
  for(int i = 0; i < M; i++) {
    scanf("%d %d", &x, &y);
    map[y].push_back(x);
  }

  for (int i = 1; i <= N; i++) {
    BFS(i);
    memset(visited, false, sizeof(visited));
  }

  for(int i = 1; i <= N; i++)
    if(mx == ans[i]) 
      printf("%d ", i);

  return 0;

}

djm03178 4년 전 1

visited[i]가 아니라 visited[map[now][i]]여야 할 것 같습니다.

luciferkala 4년 전 0

아...감사합니다! 덕분에 해결했습니다!

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

문제

문제

출처

ICPC

BFS 메모리 초과 문제

luciferkala 4년 전 0

djm03178 4년 전 1

luciferkala 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말