BOJ)9466 텀 프로젝트 (다시보기)

문제 : https://www.acmicpc.net/problem/9466

01234567891011121314151617

#include <iostream> #include <vector> #include <cstring> #include <stack> using namespace std; int test_case; int student_num; int graph[100001]; bool visited[100001]; bool finished[100001]; int cnt=0; void DFS(int now_pos) { visited[now_pos] = true; int next = graph[now_pos]; if (visited[next] == true) { // != if(vistied && finished) else 처리에서 달라진다. if (finished[next] == false) { int first_cycle_position = next; for (int i = 0; ; i++) { if (i != 0 && next == first_cycle_position) break; next = graph[next]; cnt ++; } } } else DFS(next); finished[now_pos] = true; } int main() { cin >> test_case; while (test_case--) { cin >> student_num; for (int i = 1; i <= student_num; i++) { cin >> graph[i]; } for (int i = 1; i <= student_num; i++) { if(visited[i] == false) DFS(i); } cout << student_num - cnt<<"\n"; cnt = 0; memset(graph, 0, sizeof(int) * (student_num + 1)); memset(visited, false, sizeof(bool)*(student_num+1)); memset(finished, false, sizeof(bool)*(student_num+1)); } }