[BOJ] 9466. 텀 프로젝트

*사이클이 존재함을 알 수 있어야 한다. 

*그와 동시에 팀에 몇명이 포함되는지도 알아야 한다. 

*팀에 속하지 못한 인원이 몇명인가 -> n- (팀에 속한 인원)

*part[] -> 팀원으로 택한 학생의 인덱스 (입력값)

chk[] -> 처음 시작한 학생의 인덱스 (사이클이 존재함을 알아낸다. -> 내가 처음 dfs를 시작했는데 다시 나를 택한 사람이 있다? -> 사이클)

seq[] -> 팀내의 불린 순서 (최종 인원을 알아내기 위해서 depth를 저장한다)

 

2

5

4

5

2

1번 -> 2번 호출 (chk[1] : 1, seq[1] = 0)

2번 -> 5번 호출 (chk[2] : 1, seq[2] = 1)

5번 -> 2번 호출 (chk[5] : 1, seq[5] = 2)

--> 2번이 2번 호출됐을 때 chk[2] != -1 && chk[2] == start 이므로 사이클이 존재. 

 

if (chk[now] != -1 && chk[now] != start)  -> 이미 사이클이 존재함을 알아냈는데 또 반복하지 않도록 한다. 

 

 

#include <iostream> #include <vector> #include <cstring> using namespace std; int n, res = 0; int part[100001], chk[100001], seq[100001]; void dfs(int now, int start, int cnt) { //status에는 처음 시작한 학생의 이름을 저장한다. if (chk[now] != -1 && chk[now] != start) { //사이클 끊어짐 return; } if (chk[now] == -1) { //아직 한 번도 불리지 않은 상태 chk[now] = start; seq[now] = cnt; //등장 순서를 저장 dfs(part[now], start, cnt + 1); } else { //사이클 존재 (다시 자신으로 돌아옴) res += cnt - seq[now]; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { memset(seq, 0, sizeof(seq)); cin >> n; for (int i = 1; i <= n; i++) { cin >> part[i]; chk[i] = -1; //팀이 아님 } res = 0; for (int i = 1; i <= n; i++) { dfs(i, i, 0); } /*for (int i = 1; i <= n; i++) { cout << i << " " << chk[i] << " " << seq[i] << '\n'; }*/ cout << n - res << '\n'; } return 0; }

7
6
2 3 4 5 6 2
output : 1

5
2 5 4 5 2
output : 3

6
1 3 4 3 2 6
output : 2

13
2 4 5 2 4 1 8 9 10 11 9 10 10
output : 8

10
2 5 7 1 6 8 8 3 5 10
output : 6

10
2 7 10 5 3 3 9 10 6 3
output : 8

6
2 1 1 2 6 3
output : 4