[백준][9466번] 텀 프로젝트[cpp, c++]

백준 9466번 텀 프로젝트

• 시간초과에 주의해야되는 문제이다.

• https://www.acmicpc.net/problem/9466

• 풀이 방법
  1) 한번에 탐색만에 사이클이 있고, 없고를 판단하면서 지나가야한다.
  2) 1->2->3->4->5->4 라는 것이 있으면 4,5가 사이클이다. 여기서 4,5가 사이클임을 파악해야되고, 6번으로 바로 넘어가야 시간초과가 뜨지 않는다.

 
 #include<iostream>
#include<stack>
#include<vector>
#include<string.h>
using namespace std;
int ans; 
int visited[100000]; //방문횟수 담는 배열
bool check[100000];  // 사이클을 찾았다는 뜻 
int student[100000];
int T, number;
 
void input_data() { //입력받는 함수
    cin >> number;
    int num1;
    for (int i = 1; i <= number; i++) {  //1부터 입력을 받았음.
        cin >> student[i];
    }
}
 
void cycle(int n) {
    if (visited[n] == -1 || check[n] == true) return;
    if (visited[n] == 0) visited[n] = 1;
    else if (visited[n]==1) {
        check[n] = true; //사이클 찾음
        ans++; //사이클 횟수 증가 
    }
    cycle(student[n]);
    visited[n] = -1; // 사이클 검사가 끝났으니 더 이상 방문할 필요 없다.
}
 
void sol() {
    cin >> T;
    while (T--) {
        input_data();
        for (int i = 1; i <= number; i++) if(visited[i]==0) cycle(i);
        cout <<number -ans<<'\n';
 
        //초기화
        ans = 0;
        memset(check, 0, sizeof(check));
        memset(visited, 0, sizeof(visited));
        memset(student, 0, sizeof(student));
    }
    return;
}
 
 
 
int main(void) {
    sol();
}