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;
}
}
}
}
}