글 읽기 - [C++]여러 반례들을 모두 시도해봤는데 찾을 수 가 없습니다.

gustjs2080 4년 전 0

안녕하세요.

여러 반례들을 해보았는데 잘되서 글을 쓰게 되었습니다.

어떤 반례가 있을까요 ? ㅠㅠ

감사합니다

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>

using namespace std;
int counting[100000]; // cycle인지 확인하는 배열 ex) count[n]==2 : 사이클 / count[n] == -1 사이클이 절대 아님.
int wanted[100000]; // 누구와 팀원이 되고 싶은지 저장하는 배열
int T; // 테스트 갯수
vector<int> ans; // 정답 담는 vector

/*
	0->1->2->3->2 라면
	dfs 함수에 의해서
	count[0] = 1;  
	count[1] = 1; 
	count[2] = 2;
	count[3] = 2;

	되는데
    값이 2라면 탐색과정에서 두번을 참조했다는 얘기이므로 사이클이라고 판단
    
	값이 1인 애들은 사이클이 아닌것을 확실히 알았으니 절대 사이클이 될 수 없으므로 -1로 바꾸어줌
	count[0] = -1
	count[1] = -1

*/
void dfs(int n) {
	if (counting[n] == 2 || counting[n] ==-1)
		return;
	counting[n]++;
	dfs(wanted[n]);

	if (counting[n] == 1)
		counting[n] = -1;
}
int main() {
	cin >> T;
	int n;
	int answer;
	for (int t = 0; t < T; t++) {
		cin >> n;
		answer = 0;
		fill(counting, counting + n, 0); // 테스트 케이스마다 0으로 초기화
		

		for (int i = 0; i < n; i++) {
			cin >> wanted[i];
			--wanted[i];
		}

		for (int i = 0; i < n; i++) {
			dfs(i);
		}

		for (int i = 0; i < n; i++)
			if (counting[i] != 2) // 사이클이 아닐 경우 count
				answer++;
		ans.push_back(answer);
	}

	for (int i = 0; i < ans.size(); i++)
		printf("%d\n", ans[i]);
}

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

문제

문제

출처

ICPC

[C++]여러 반례들을 모두 시도해봤는데 찾을 수 가 없습니다.

gustjs2080 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말