글 읽기 - 어디 부분에서 잘못된 걸까여?

zpapl 5년 전 0

입력을 인접리스트로 표현하고 각 정점마다 도달할 수 있는 정점의 개수를 계산하도록 구현했는데

계속 출력 초과가 발생합니다.

어디가 잘 못된걸까여?

#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

int N, M;
int A, B;
vector<vector<int>> adj;
vector<bool> visited;
vector<pair<int, int>> answer;

bool Comp(pair<int, int> a, pair<int, int> b) {
	if (a.first == b.first) {
		return a.second < b.second;
	}

	return a.first > b.first;
}

int dfs(int computer) {
	int num_visit = 1;

	for (int i = 0; i < adj[computer].size(); i++) {
		int next_computer = adj[computer][i];
		if (!visited[next_computer]) {
			visited[next_computer] = true;
			num_visit += dfs(next_computer);
		}
	}

	return num_visit;
}

int main() {
	scanf("%d%d", &N, &M);


	adj.resize(N);
	visited.resize(N, false);
	answer.resize(N);

	for (int i = 0; i < M; i++) {
		scanf("%d%d", &A, &B);
		A--; B--; //인덱스 0부터 시작하도록 맞추는 작업

		adj[B].push_back(A);
	}

	for (int i = 0; i < N; i++) {
		visited.clear();
		visited.resize(N, false);
		answer[i] = make_pair(dfs(i), i + 1);
	}

	sort(answer.begin(), answer.end(), Comp);

	printf("%d ", answer[0].second);

	for (int i = 1; answer.size(); i++) {
		if (answer[i].first == answer[0].first) {
			printf("%d ", answer[i].second);
		} else {
			break;
		}
	}

	return 0;
}

jh05013 5년 전 0

출력 초과 이전에 답도 잘못 나옵니다.

https://www.acmicpc.net/board/...

무한 출력이 나지 않더라도 정답에 비해 많은 수를 출력하면 출력 초과이므로, 이 경우일 가능성이 높아 보입니다.

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

문제

문제

출처

ICPC

어디 부분에서 잘못된 걸까여?

zpapl 5년 전 0

jh05013 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말