글 읽기 - 시간초과 문제 떄문에 문의드립니다..!

seyoung1219 4년 전 0

하아..

시간초과문제 해결할려고 진짜 답 안보고 4시간 하다가 현타와서 질문합니다 ㅜㅜ

아래의 코드 같이 작성하면 채점 80%에서 시간초과 뜹니다 ㅜㅜ

무엇을 잘 못했는지.. 봐주시면 감사하겠습니다 ㅜㅜ

#include <iostream>
#include <vector>

using namespace std;


vector<int> team;
int T, N, *visit, *graph, result;

bool DFS(int s) {

	for (unsigned int j = 0; j < team.size(); j++) {
		if (team[j] == s) {
			result -= team.size() - j;
			return true;
		}
	}

	team.push_back(s);

	int next = graph[s];
	if (visit[next] == 0) {
		if (DFS(next)) {
			visit[next] = 1;
			return true;
		}
		else {
			return false;
		}
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);


	cin >> T;
	while (T-- > 0) {
		cin >> N;
		result = N;

		graph = new int[N + 1];
		visit = new int[N + 1];
		fill_n(visit, N + 1, 0);
		fill_n(graph, N + 1, 0);

		for (int i = 1; i <= N; i++) {
			int input;
			cin >> input;
			graph[i] = input;
		}

		for (int i = 1; i <= N; i++) {
			if (visit[i] == 0) {
				DFS(i);
			}

			team.clear();
		}

		cout << result << '\n';
	}

	return 0;
}

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

문제

문제

출처

ICPC

시간초과 문제 떄문에 문의드립니다..!

seyoung1219 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말