9466 Term project

์•Œ๊ณ ๋ฆฌ์ฆ˜ (DFS, ๊ทธ๋ž˜ํ”„)

1. ๊ฐ ํ•™์ƒ๋“ค์ด ๊ฐ€๋ฆฌํ‚ค๋Š” ํ•™์ƒ์„ ์ €์žฅํ•œ student ๋ฐฐ์—ด, cycle์— ๋ช‡๋ช…์ด ์žˆ๋Š”์ง€ ์ฒดํฌํ•˜๋Š” cycleCcount ๋ณ€์ˆ˜, ์‚ฌ์ดํด์ด ํ˜•์„ฑ๋๋Š”์ง€ ํ™•์ธํ•˜๋Š” cycleCheck boolํ˜• ๋ฐฐ์—ด.
   ๊ฒ€์‚ฌ์ค‘์ธ ํ•™์ƒ๋“ค์„ ์ €์žฅํ•˜๋Š” q๋ฐฐ์—ด
2. ์ฒซ๋ฒˆ์งธ ํ•™์ƒ๋ถ€ํ„ฐ ๊ฒ€์‚ฌ
	-student๊ฐ€ -1 ์ด๋ฉด ๊ฒ€์‚ฌ์•ˆํ•จ. (์ด๋ฏธ ๊ฒ€์‚ฌ๋œ ๊ฒƒ)
	-๊ฒ€์‚ฌ๊ฐ€ ์‹œ์ž‘๋˜๋ฉด, q์— ๋„ฃ๊ณ , cycleCheck ๋ฐฐ์—ด์— ํ‘œ์‹œํ•˜๊ณ , start์—” ์ž๊ธฐ, end์—” ๋‹ค์Œ๊ฑธ ๊ฐ€๋ฆฌํ‚ค๋ฉฐ, ๊ทธ๋ž˜ํ”„๋”ฐ๋ผ dfs ์‹œ์ž‘
	-๊ทธ๋ž˜ํ”„ ๋”ฐ๋ผ๊ฐ€๋ฉด์„œ cycleCheck์— ํ‘œ์‹œ, end๋Š” ํ•ญ์ƒ ๋‹ค์Œ ๊ฑธ ๊ฐ€๋ฆฌํ‚ค๊ฒŒ ํ•จ.
	-end๊ฐ€ -1์ด๊ฑฐ๋‚˜, ์ด๋ฏธ ๊ฒ€์‚ฌํ•œ ๊ฑฐ๋ฉด ์ข…๋ฃŒ
	-start์™€ end๊ฐ€ ๊ฐ™์œผ๋ฉด ์‹œ์ž‘๋ถ€ํ„ฐ ์‚ฌ์ดํด ํ˜•์„ฑ๋œ ๊ฒƒ.
		- q์— ๋„ฃ์–ด์ง„ ๊ณณ์„ ์ „๋ถ€ -1๋กœ ๋ฐ”๊พธ๊ณ , count๋ฅผ qํฌ๊ธฐ๋งŒํผ ์ฆ๊ฐ€์‹œํ‚ด
	-๋‹ค๋ฅด๋ฉด end๊ฐ€ -1์ด ์•„๋‹Œ ๊ฒฝ์šฐ์—” ์ค‘๊ฐ„์— ์‚ฌ์ดํด๋งŒ ๋„ฃ์–ด์ฃผ๊ณ , ์ „๋ถ€ -1๋กœ ๋ณ€๊ฒฝ
		-1์ด๋ฉด ๊ทธ๋ƒฅ ์ „๋ถ€ -1๋กœ ๋ณ€๊ฒฝ

์ฝ”๋“œ

#include <iostream>
#include <cstring>
#define MAX_STUDENT 100000
 
using namespace std;
 
int numOfStudent, student[MAX_STUDENT+1];
bool checkCycle[MAX_STUDENT+1];
int queue[MAX_STUDENT + 1], cycleCount;
 
void generateCheck();
 
int main() {
	int tc;
	cin >> tc;
	for (int i = 0; i < tc; i++) {
		cin >> numOfStudent;
		for (int j = 1; j <= numOfStudent; j++)
			cin >> student[j];
 
		cycleCount = 0;
		generateCheck();
		cout << numOfStudent - cycleCount << endl;
	}
}
void generateCheck() {
	for (int i = 1; i <= numOfStudent; i++) {
		if (student[i] != -1) {
			int start = i;
			int end = student[i];
			int index = 0;
			queue[index++] = i;
			checkCycle[start] = true;
			while (!checkCycle[end]) {
				queue[index++] = end;
				checkCycle[end] = true;
				end = student[end];
				if (end == -1)
					break;
			}
 
			if (start == end) {
				for(int j = 0; j<index; j++) {
					cycleCount++;
					student[queue[j]] = -1;
					checkCycle[queue[j]] = false;
				}
			}
			else {
				int j = index - 1;
				if (end != -1) {
					for (; j >= 0; j--) {
						if (queue[j] != end) {
							cycleCount++;
							student[queue[j]] = -1;
							checkCycle[queue[j]] = false;
						}
						else
							break;
					}
					cycleCount++;
				}
				for(; j>= 0; j--) {
					checkCycle[queue[j]] = false;
					student[queue[j]] = -1;
				}
			}
		}
	}
}