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

yepp0112 3년 전 0

이 문제 dfs로 풀려 했는데 메모리 초과가 떠 버리네요ㅠㅠ

시간초과나 틀렸습니다는 많이 봤는데 메모리 초과가 뜨니 답답하네요.

무엇이 잘못됐을까요...??

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>

using namespace std;

int n,m;

vector<int> v[10001];

bool visit[10001]={false, };

int dep[10001];

int dfs(int num,int depth){
	if(v[num].size()==0){
		dep[num]=0;
		visit[num]=true;
		return dep[num];
	}
	
	else if(visit[num]==true){
		return dep[num];
	}
	
	for(int i=0;i<v[num].size();i++){
		int y=v[num][i];
		
		dep[num]=max(dep[num],1+dfs(y,depth+1));
	}
	
	visit[num]=true;
	
	return dep[num];
}

int main (){
	ios_base :: sync_with_stdio;
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin>>n>>m;
	
	int i;
	
	for(i=0;i<m;i++){
		int a,b;
		
		cin>>a>>b;
		
		v[a].push_back(b);
	}
	
	int m=10001;
	
	for(i=1;i<=n;i++){
		if(visit[i]==true) continue;
		
		if(m>dfs(i,0)) m=dfs(i,0);
		
		visit[i]=true;
	}
	
	//cout<<"max : "<<m<<'\n';
	
	for(i=1;i<=n;i++){
		if(m==dep[i]) cout<<i<<' ';
	}
	return 0;
}

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

문제

문제

출처

ICPC

dfs 메모리 초과문제

yepp0112 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말