아이디어

• 사이클을 감지해야한다는 점에서 위상정렬을 시도해봤다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;
	
	static int T, n, ans;
	static int[] A;
	
	static Queue<Integer> q = new ArrayDeque<>();
	static int[] indeg;

	public static void main(String[] args) throws Exception {
		T = Integer.parseInt(rd.readLine());
		for (int t=1; t<=T; t++) {
			n = Integer.parseInt(rd.readLine());
			
			A = new int[n+1];
			indeg = new int[n+1];
			tk = new StringTokenizer(rd.readLine());
			for (int i=1; i<=n; i++) {
				A[i] = Integer.parseInt(tk.nextToken());
				indeg[A[i]]++;
			}

			ans = 0;
			q.clear();
			for (int i=1; i<=n; i++) {
				if (indeg[i] == 0) {
					q.add(i);
					ans++;
				}
			}
			
			while (!q.isEmpty()) {
				int n = q.poll();
				indeg[A[n]]--;
				if (indeg[A[n]] == 0) {
					q.add(A[n]);
					ans++;
				}
			}
			
			sb.append(ans).append('\n');
		}
		System.out.println(sb);
	}


}

메모리 및 시간

• 메모리: 305408 KB
• 시간: 1104 ms

리뷰

• 2668번(내 풀이)이랑 같은 문제인 줄 알았는데, N의 범위가 훨씬 더 커서 당황스러웠다.
• 풀긴 풀었는데, 메모리와 시간을 봐서 정해는 아닌 것 같다. 더 효율적인 풀이를 찾아봐야겠다. 혹시 똑같이 풀면 풀리나?