글 읽기 - 도움이 필요합니다

ohyeons 4년 전 0

순회를 돌면서 사이클이 만들어지지 않는 경우는 방문 배열만

그외 의 경우는 사이클배열에 true 로 저장했는데 틀렸습니다가 나오네요.... 어디서 잘못된걸까요

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <tuple>
using namespace std;
int T, n;
int arr[100001];
bool V[100001];//방문만 체크
bool E[100001];//사이클에 포함되어 더이상 볼필요 없는경우
vector<int>v;
void DFS(int start, int next) {
	if (start == next) {//시작 정점과 다음 가야할 정점이 같으면 사이클(그룹)완성
		for (int i = 0; i < v.size(); i++) {
			E[v[i]] = true;
		}
		return;
	}
	if (!V[next])//한번도 방문 안한 경우
	{
		V[next] = true;
		v.push_back(next);//방문한 정점들 저장
		DFS(start, arr[next]);//다음 정점으로 넘어가기
	}
	else if (V[next] && !E[next]) {
		//방문은 한번했는데 또 방문 하는 경우>>사이클 형성
		//start!=next 이지만 중간에서 사이클이 형성되는 경우
		int temp;
		for (int i = 0; i < v.size(); i++) {
			if (v[i] == next) { temp = i; break; }
		}
		for (int i = temp; i < v.size(); i++) {
			E[v[i]] = true;
		}
		return;
	}
	

}
int main() {
	/*ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);*/
	//cin >> T;
	scanf("%d", &T);
	while (T--) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
			if (arr[i] == i) {//자기 자신을 가르키는 경우는 그냥 끝
				V[i] = true;
				E[i] = true;
			}
		}
		for (int i = 1; i <= n; i++) {
			if (!V[i] && !V[arr[i]] &&!E[i]) {
				//자기 자신과 자신이 가르키는 상대 모두 그룹이 안된경우 탐색
				V[i] = true;  v.push_back(i); DFS(i, arr[i]); v.clear();
			}
		}
		int count = 0;
		for (int i = 1; i <= n; i++) {//그룹이 안된 아이들 체크와 동시에 방문배열 초기화
			if (!E[i])count++;
			E[i] = false;
			V[i] = false;
		}
		//cout << count << "\n";
		printf("%d\n", count);
		v.clear();
	}
	return 0;
}

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

문제

문제

출처

ICPC

도움이 필요합니다

ohyeons 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말