9466 Term project
알고리즘 (DFS, 그래프)
1
2
3
4
5
6
7
8
9
10
11
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로 변경
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#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;
}
}
}
}
}