#9446번 텀 프로젝트 (C++)

링크 : www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

이 문제의 풀이는 #2668번 숫자고르기 (C++)와 동일하며(링크 참조), 

숫자고르기를 이해하면 텀 프로젝트 문제또한 일사천리로 해결이 가능하다.

 

다만 유의해야할 점은 다음과 같다. 

 

(1) 학생의 최대수는 100,000명이므로, 메모리 관리에 신경을 써야한다. 

(2) 테스트 케이스만큼 반복적으로 실행된다. 즉, 같은 함수 + 변수를 공유해야 메모리 관리가 가능하다.

(3) 팀플이 가능한 학생이 아니라 불가능한 학생수를 출력하는 것이다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int test = 0, ans = 0;
vector<int> s;
bool check[100001];
bool fin[1000001];

void dfs(int i) {
    check[i] = true;
    if (!check[s[i]]) {
        dfs(s[i]);
    }
    else if (!fin[s[i]]) {
        ans++;
        for (int j = s[i]; j != i; j = s[j]) ans++;
    }
    fin[i] = true;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int cnt = 0, temp = 0, num = 0;
    cin >> test;
    while (cnt < test) {
        cin >> num;
        s.push_back(0);
        for (int i = 1; i <= num; i++) {
            cin >> temp;
            s.push_back(temp);
        }
        for (int i = 1; i <= num; i++) {
            if (!check[i]) {
                dfs(i);
            }
        }
        cout << num-ans << "\n";
        ans = 0;
        memset(check, false, sizeof(check));
        memset(fin, false, sizeof(fin));
        s.clear();
        cnt++;
    }

    return 0;
}

memset을 통한 초기화를 잊지말아야한다.