글 읽기 - 10451_순열사이클, 시간초과가 납니다

sjsjsj1246 5년 전 0

첫번째 코드는 시간초과가 났고 두번째 코드는 통과됐습니다.

첫번째 코드는 벡터를 통해 간선을 저장했고 두번째 코드는 전역 배열로 저장을 했습니다.

벡터의 사용이 뭔가 문제가 있는 건가요?

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

//시간초과
bool visited[1001];

int dfs(int here, vector<int> adj)
{
	int next = adj[here];
	visited[here] = true;
	if (visited[next] == true) return 1;
	return dfs(next, adj);
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		memset(visited, false, sizeof(visited));
		int n, sum = 0, temp;
		cin >> n;

		vector<int> adj;
		for (int i = 0; i < n; i++) cin >> temp, adj.push_back(temp - 1);
        /*
        vector<int> adj(n);
		for (int i = 0; i < n; i++) cin >> adj[i], adj[i]--;
        이렇게 해도 시간초과
        */
		for (int i = 0; i < n; i++)
		{
			if (!visited[i])
			{
				sum += dfs(i, adj);
			}
		}
		cout << sum << "\n";
	}
}

//------------------------------------------------------------------
//통과
bool visited[1001];
int adj[1001];

int dfs(int here)
{
	int next = adj[here];
	visited[here] = true;
	if (visited[next] == true) return 1;
	return dfs(next);
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		memset(visited, false, sizeof(visited));
		int n, sum = 0, temp;
		cin >> n;

		for (int i = 0; i < n; i++) cin >> temp, adj[i] = temp - 1;
		for (int i = 0; i < n; i++)
		{
			if (!visited[i])
			{
				sum += dfs(i);
			}
		}
		cout << sum << "\n";
	}
}

seico75 5년 전 1

dfs 에 벡터를 넘기는 것이 문제인 것 같습니다.

벡터가 복사가 될 것 같은데 재귀로 여러번 들어가면 속도저하가 심할 것 같습니다.

sjsjsj1246 5년 전 0

그렇군요! 감사합니다.

첫번째 코드에서

int dfs(int here, vector& adj)

로 바꿨더니 통과됐습니다.

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

문제

문제

출처

ICPC

10451_순열사이클, 시간초과가 납니다

sjsjsj1246 5년 전 0

seico75 5년 전 1

sjsjsj1246 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말