9466번: 텀 프로젝트

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


$O(tn)$

사이클을 이루지 않는 학생들 수를 구하면 된다.
이를 구하기 위해 들어오는 간선이 없는 학생들을 계속 제거하자. 이 과정은 위상정렬과 비슷하다.

#include<stdio.h>
const int MAX_N = 1e5;
int t, n, ind[MAX_N + 1], nxt[MAX_N + 1], ck[MAX_N + 1];
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        int h, r = 0;
        for (int i = 1; i <= n; i++) ind[i] = ck[i] = 0;
        for (int i = 1; i <= n; i++) scanf("%d", nxt + i), ind[nxt[i]]++;
        for (int i = 1; i <= n; i++) {
            h = i;
            while (!ind[h] && !ck[h]) {
                ck[h] = 1;
                ind[nxt[h]]--;
                h = nxt[h];
                r++;
            }
        }
        printf("%d\n", r);
    }
    return 0;
}