글 읽기 - 5%에서 틀렸습니다가 나옵니다.. 제발 도와주세요

wjddms206 7년 전 0

어떤 부분이 틀렸을까요??? ㅠㅠ

예는 다 해봤는데 도저히 못찾겠습니다.

너무 답답합니다 도와주세요...

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

int arr[100001];
bool visit[100001];
bool ret[100001];
bool flag;
int cycleVertex;

void dfs(int vertex)
{
	visit[vertex] = true;

	int adj = arr[vertex];
	if (vertex == adj) { // 자기 자신을 가리키고 있을때
		ret[adj] = true;
		return;
	}
	if (!visit[adj] && !ret[adj]) {
		dfs(adj);
		if(cycleVertex == vertex) // 싸이클 생기는 정점에서 return될때는 visit을 false로 해주기 위해서
			flag = false;
	}
	else if(!ret[adj]) {
		ret[adj] = true;
		flag = true;
		cycleVertex = adj; // 싸이클 생기는 정점을 저장
		return;
	}
	
	if(!flag) 
		visit[vertex] = false;
}

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

	while (tc--) {
		int n;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			int a;
			scanf("%d", &a);
			arr[i] = a;
			ret[i] = 0;
			visit[i] = 0;
		}
		for (int i = 1; i <= n; i++) {
			flag = false;
			cycleVertex = 0;
			if (!visit[i]) {
				dfs(i);
			}
			else ret[i] = true;
		}
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			//cout << ret[i] << ' ';
			if (ret[i] == false) cnt++;
		}
		printf("%d\n", cnt);
	}
	return 0;
}

pichulia 7년 전 3

이런 반례가 있겠네요..

5
5 3 4 5 1

먼저 싸이클을 하나 만들고나면

ret[i] == 0이고 visit[i] == 1인 정점들이 우다다다 생기고

만약 이런 정점을 향해가는 친구가 있을 경우

자기가 사이클 위에 있는줄 알고 착각해버리네요.

wjddms206 7년 전 0

감사합니다 다시한번 생각해보겠습니다!

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

문제

문제

출처

ICPC

5%에서 틀렸습니다가 나옵니다.. 제발 도와주세요

wjddms206 7년 전 0

pichulia 7년 전 3

wjddms206 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말