텀 프로젝트

• 사이클이 생기면 그 사이클이 팀이 된다. 따라서 그냥 사이클들을 모두 찾아주고, 그러면서 사이클들의 길이들을 모두 구해서 더해준 다음에 전체 길이에서 빼면 사이클에 속하지 못한 학생의 수가 된다.
• 사이클을 찾는 것은 그냥 선택한 학생들 따라서 순회하면서 체크를 해주다가, 체크된 학생을 방문하게 되면 사이클로 처리하면 된다. 지난 탐색에서 방문한 학생들과 구분하기 위해서, 체크할때 id를 다르게 해줘야 한다. 그리고 방문한 순서도 저장해두면 사이클의 길이를 바로 구할수 있다. 모든 사이클을 찾는 시간복잡도는 O(n)이 된다.
• 하지만 좀더 간단하면서 살짝 더 빠른 방법이 있다. 각 학생들의 선택받은 횟수를 구해놓는다. 선택받은 횟수가 0인 학생들은 사이클에 포함되어 있지 않다. 이 학생들을 따로 큐에 저장해둔뒤, 이 학생들을 하나씩 지우면서 이 학생이 선택했던 학생의 선택받은 횟수를 감소시킨다. 이렇게 하면서 선택받은 횟수가 0이 된 학생이 생기면 큐에 추가한다. (위상 정렬 (Topological Sorting)에서 사용하는 알고리즘이랑 같다). 큐가 다 비워지면, 그때까지 안지워진 학생들이 사이클에 포함된 학생들이다. 이방법 역시 시간복잡도는 O(n)이다.
• 실제 코드는 후자로 구현한 방법만 첨부.

"""Solution code for "BOJ 9466. 텀 프로젝트".

- Problem link: https://www.acmicpc.net/problem/9466
- Solution link: http://www.teferi.net/ps/problems/boj/9466
"""

import sys


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        n = int(sys.stdin.readline())
        selects = [int(x) for x in sys.stdin.readline().split()]

        indegrees = [0] * n
        for i in selects:
            indegrees[i - 1] += 1
        leaves = [i for i, indegree in enumerate(indegrees) if indegree == 0]
        while leaves:
            next_stu = selects[leaves.pop()] - 1
            indegrees[next_stu] -= 1
            if indegrees[next_stu] == 0:
                leaves.append(next_stu)

        print(n - sum(indegrees))


if __name__ == '__main__':
    main()