[アルゴリズム]Java/バックアップ/データムアイテム/9466


[アルゴリズム]Java/バックアップ/データムアイテム/9466


質問する
質問リンク
コード#コード#
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_9466 {

	static int selects[];
	static int solo;
	static boolean finished[];
	static boolean visited[];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;
		for(int tc=0;tc<T;tc++) {
			int n = Integer.parseInt(br.readLine());
			
			st = new StringTokenizer(br.readLine());
			
			selects = new int[n+1];
			
			for(int i=1;i<=n;i++) {
				selects[i] = Integer.parseInt(st.nextToken());
			}
			
			solo = n;
			
			finished = new boolean[n+1];
			visited = new boolean[n+1];
			
			for(int i=1;i<=n;i++) {
				if(!visited[i]) dfs(i);
			}
			
			sb.append(solo+"\n");
		}
		System.out.print(sb); 
	}
	
	public static void dfs(int node) {
		// 현재 노드 방문처리
		visited[node] = true;
		
		// 다음 노드 저장
		int nextNode = selects[node];
		
		// 다음 학생을 방문하지 않았다면
		if(!visited[nextNode]) {
			dfs(nextNode);
		}
		// 방문했다면 (싸이클인 경우)
		else {
			// 검사를 안받았다면
			if(!finished[nextNode]) {
				
				solo--;
				
				while(nextNode != node) {
					nextNode = selects[nextNode];
					solo--;
				}
			}
		}
		finished[node] = true;
	}
	
	

}