글 읽기 - 98%에서 시간초과가 납니다..

kimbregas 7년 전 0

안녕하세요.

DFS를 구현해서 풀고 있습니다. 첫번째 방문시 1(그룹없음), 두번째 방문시 2(그룹있음), 세번째 방문한다면 이는 cycle이 생긴 것이 확실시 되니

그때, DFS를 종료하게 됩니다. 이런식으로 구현하였는 데, 98%에서 시간초과가 났습니다.

어떤 부분에서 잘못이 되었는지 궁금합니다!

#include<cstdio>
#include<cstring>

using namespace std;

int alone[100001]; // -1 ->아직 결정x, False->그룹있음., True-> 그룹 없고 혼자있음.
int student[100001];
int check[100001] = { 0, };  //0-> 방문한적x, 1-> 첫방문, 2->두번째방문(cycle발생시점)

void DFS(int vertex) {
	check[vertex] += 1;

	if (check[vertex] == 1) {
		alone[vertex] = true;
	}
	else if (check[vertex] == 2) {
		alone[vertex] = false;
	}
	else if (check[vertex] == 3)//cycle발생확실시.
		return;

	DFS(student[vertex]);
}
int main() {
	
	int t;
	scanf("%d", &t);

	memset(alone, -1, sizeof(alone));

	while (t--) {
		int n;
		scanf("%d", &n);

		for (int i = 1; i <= n; i++) {
			scanf("%d", &student[i]);
		}

		for (int i = 1; i <= n; i++) {
			if (alone[i] == -1) { //아직 결정 안된 학생들만
				if (alone[student[i]] != -1) { //지정할려고 한 학생이 이미 그룹에 속해있던가, 혼자이면 alone.
					alone[i] = true;
				}
				else {
					DFS(i);
				}
			}
		}

		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			if (alone[i])
				cnt++;
		}

		printf("%d\n",cnt);

		for (int i = 1; i <= n; i++) { //초기화
			check[i] = 0;
			alone[i] = -1;
			student[i] = 0;
		}
	}
}

lilililiiiiiiii 6년 전 0

저도 DFS로 98%에서 시간 초과가 나네요.. ㅠ_ㅠ

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

문제

문제

출처

ICPC

98%에서 시간초과가 납니다..

kimbregas 7년 전 0

lilililiiiiiiii 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말