글 읽기 - 1%에서 시간초과가 발생합니다.

cleankid99 4년 전 0

dfs로 구현을 하였고

앞에서 확인한 정보를 dp처럼 활용하여

cycle이었는지, cycle이 아니었는지 확인하는 절차도 거치고

loop (3->3) 인 경우는 처음부터 조치를 취해주었습니다.

바로 시간초과가 날 거라고는 생각하지 못했는데

어떤 부분을 수정해야할까요?

#include <cstdio>
#include <vector>
using namespace std;

vector<vector<int> > adj;
vector<bool> chk;
vector<bool> lp;
vector<int> tmp;
vector<bool> arr;

int t, n, cycle = 0, cnt = 0, cur;

void dfs(int num) {
	if (arr[num] == false && num < cur) { // 앞에서 이미 cycle이 아닌지 확인했다면
		return;
	}
	if (arr[num] == true) { // 이미 cycle이라면
		return;
	}
	if (lp[num] == true) { // loop라면 no cycle
		chk[num] = true;
		return;
	}	
	else {
		chk[num] = true;
		tmp.push_back(num); // 임시로 저장 , cycle일 경우에 배열에 저장
		for (int i = 0; i < adj[num].size(); i++) {
			int next = adj[num][i];
			if (!chk[next]) {
				dfs(next);
			}
			else if (chk[next] && cur == next) {// cycle 생성완료
				cycle = 1;
				return;
			}
		}
	}
	return;
}

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

	while (t--) {		
		scanf("%d", &n);
		adj.resize(n + 1);
		chk.resize(n + 1);
		lp.resize(n + 1);
		arr.resize(n + 1);
		cnt = n;

		for (int i = 1; i <= n; i++) {
			int temp;
			scanf("%d", &temp);
			adj[i].push_back(temp);
			if (temp == i) { // loop
				lp[i] = true;
				arr[i] = true; // loop도 cycle이므로 바로 저장
			}
		}

		for (int i = 1; i <= n; i++) {
			cur = i; // 현재 인덱스 저장
			dfs(i);
			if (cycle == 1) { // cycle이 생성되었을 경우
				while (tmp.size()) {
					arr[tmp.back()] = true;
					tmp.pop_back();
				}				
			}
			chk.clear();
			chk.resize(n + 1);
			tmp.clear();
			cycle = 0;
		}

		for (int i = 1; i <= n; i++) {
			if (arr[i] == true) {
				cnt--;
			}
		}
		
		printf("%d\n", cnt);

		adj.clear();
	}


	return 0;
}

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

문제

문제

출처

ICPC

1%에서 시간초과가 발생합니다.

cleankid99 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말