글 읽기 - 런타임 에러 나는데 도움 좀 부탁드립니다..

harry1992 5년 전 0

안녕하세요 DFS로 끝까지 파고 들어가서 numbering 역순으로 하는 형태로 코드 짜봤는데요..

예시는 도는데 제출하니 런타임 에러가 뜨네요. 아시는 분들 도와주시면 정말 감사하겠습니다ㅠㅠ.

#include <iostream>
#include <stack>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
int numbering[32001];
bool check[32001];
int cnt;


void dfs(int num, vector<int>* vec) {
	//1 ) 이미 numbering이 되어 있다 
	//2 ) outgoing edge가 없다 혹은 outgoing edge 를 다 numbering 완료했다 ->자기자신 numbering하고 return 
	//3 )  outgoing edge가 존재한다. 
	bool noOutEdge;
	//outgoing edge가 없는 경우 
	if (vec[num].size() == 0)
		noOutEdge = true;
	else
		noOutEdge = false;
	
	bool checkedAllEdge=true;

	//outgoing edge가 있는데 다 쓴 경우  
	for (int i = 0; i < vec[num].size(); i++) {
		if (check[vec[num][i]] == false) {
			checkedAllEdge = false;
			break;
		}
	}
	
	if (noOutEdge || checkedAllEdge) {
		numbering[cnt] = num;
		check[num] = true;
		cnt--;
		return;
	}
	else {
		for (int i = 0; i < vec[num].size(); i++)
			dfs(vec[num][i], vec);
		numbering[cnt] = num;
		check[num] = true;
		cnt--;

	}

}


int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n >> m;
	cnt = n;
	vector<int> vec[32001];
	vector<int> reverse_vec[32001];
	vector<int> dfs_list;
	//directed graph 
	//reverse mode 
	for (int i = 0; i < m; i++) {
		int v1, v2;
		cin >> v1 >> v2;
		vec[v1].push_back(v2);
		reverse_vec[v2].push_back(v1);
	}

	for (int i = 1; i <= n; i++) {
		//incoming edge가 없다는 의미
		if (reverse_vec[i].size() == 0) {
			dfs_list.push_back(i);
		}
	}

	for (int i = 0; i < dfs_list.size(); i++)
		dfs(dfs_list[i], vec);

	for (int i = 1; i <= n; i++) {
		cout << numbering[i] << " ";
	}
	cout << '\n';
	

	return 0;
}

harry1992 5년 전 0

recursive로 짜서 stack overflow 났었네요

stack으로 iterative 형식으로 짜니까 맞게 나와요~

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

문제

문제

출처

ICPC

런타임 에러 나는데 도움 좀 부탁드립니다..

harry1992 5년 전 0

harry1992 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말