글 읽기 - 9466 메모리 초과

arakim97 2년 전 0

dfs를 통해서 각 노드를 탐방한 후 사이클이 발생되는지 확인해 정답을 확인해봤습니다

게시판의 예시들은 모두 통과한거 같은데 메모리 초과가 발생하네요

어딜 수정해야 하는지 가르쳐주실 수 있을까요?

#include <iostream>
#include <vector>

using namespace std;

void dfs(vector<int>* _graph, bool* _visited, int _node, int _start, bool* _is_cycle, int* _cycle_count){
  if(_visited[_node] == false){
    _visited[_node] = true;
    *_cycle_count  += 1;

    for(int i = 0; i < _graph[_node].size(); i++){
      int next_node = _graph[_node][i];
      if(next_node == _start){
        *_is_cycle = true;
      }
      dfs(_graph, _visited, next_node, _start, _is_cycle, _cycle_count);
      
      if(!*_is_cycle){
        _visited[_node] = false;
      }
    }
  }
  else{
    return;
  }
}

int main(){
  int testcase;

  cin >> testcase;

  for(int t = 0; t< testcase; t++){
    int stu_count;
    cin >> stu_count;
    int answer = stu_count;
    
    vector<int>* graph = new vector<int>[stu_count + 1];
    bool* visited = new bool[stu_count + 1];
    visited[0] = false;

    for(int i = 1; i <= stu_count; i++){
      int num;
      cin >> num;
      graph[i].push_back(num);
      visited[i] = false;
    }
    visited[0] = false;

    for(int i = 1; i <= stu_count; i++){
      int cycle_count = 0;
      bool is_cycle = false;
      
      if(visited[i] == false){
        dfs(graph, visited, i , i, &is_cycle, &cycle_count);
      }
      

      if(is_cycle){
        answer -= cycle_count;
      }
    }
    delete[] visited;
    cout << answer << endl;
  }
  return 0;
}

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

문제

문제

출처

ICPC

9466 메모리 초과

arakim97 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말