글 읽기 - 어떤 반례가 있을까요?

pkc4913 5년 전 0

DFS를 이용하여 위상정렬로 풀었습니다.

혹시 어떤 반례가 있을까요?

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

int bt[1001];
int total_bt[1001];
vector<int> v[1001];
int indegree[1001];
int object;
int copy_ind[1001];
void dfs(int index) {
	for (int i = 0; i < v[index].size(); i++) {
		int next = v[index][i];
		total_bt[next] = max(total_bt[next], total_bt[index] + bt[next]);
		copy_ind[next]--;
		if (copy_ind[next]) return; //진입 차수가 0이 아니라면 return
		dfs(next);
	}
}
int main()
{
	int T; cin >> T;
	while (T--) {
		//초기화 시작
		fill(bt, bt + 1001, 0);
		fill(total_bt, total_bt + 1001, 0);
		fill(indegree, indegree + 1001, 0);
		object = 0;
		for (int i = 0; i < 1001; i++) {
			v[i].clear();
		}
		//초기화 끝
		int N, K; cin >> N >> K;
		for (int i = 1; i <= N; i++) {
			cin >> bt[i];
		}
		for (int i = 0; i < K; i++) {
			int from, to;  scanf("%d %d", &from, &to);
			v[from].push_back(to);
			indegree[to]++;
		}
		cin >> object;
		copy(indegree, indegree + 1001, copy_ind); //여기다가 복사
		for (int i = 1; i <= N; i++) {
			if (!indegree[i]) {
				total_bt[i] = bt[i];
				dfs(i); //진입차수가 0이면
			}
		}
		printf("%d\n", total_bt[object]);
	}
}

djm03178 5년 전 1

19번째 줄, 과연 return을 하는 것이 맞을까요?

pkc4913 5년 전 0

감사합니다

그럼 이문제는 DFS로는 못푸는건가요?

djm03178 5년 전 0

"return을 하는 것이 맞을까요?"라는 말은, 이 자리에 다른 걸 넣으면 맞는다는 뜻이겠죠?

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

문제

문제

출처

ICPC

어떤 반례가 있을까요?

pkc4913 5년 전 0

djm03178 5년 전 1

pkc4913 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말