[백준] 9466 텀 프로젝트 [자바]

---

https://bcp0109.tistory.com/32

백준 9466번. 텀 프로젝트 (Java)

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static boolean[] visit;
	static boolean[] search;
	static boolean[] solo;
	static int cnt = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		while(T --> 0) {
			cnt = 0;
			int N = Integer.parseInt(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int[] arr = new int[N+1];
			visit = new boolean[N+1];
			search = new boolean[N+1];
			solo = new boolean[N+1];
			for(int i = 1; i <= N; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
				if(i == arr[i]) {
					solo[i] = true;
					cnt++; //혼자 소속된 팀
				}
			}
			for(int i = 1; i <= N; i++) {
				if(!search[i]) {
					dfs(i,arr);
				}
			}
			sb.append(N-cnt).append('\n');
		}
		System.out.println(sb);
	}
	static void dfs(int depth, int[] arr) {
		if(search[depth] == true) { //사이클에 포함되지 않은 학생이 사이클에 포함된 학생을 선택했을때
			return;
		}
		int choice = arr[depth];
		visit[depth] = true;
		search[depth] = true;
		if(!visit[choice]) { //방문하지 않았다면
			dfs(choice, arr);
		}
		else if(!solo[choice]){ //방문했다면(사이클을 형성한다) 혼자 소속된 팀은 제외
			cnt++; //사이클의 마지막 476에서 6을 먼저 추가
			for(int i = choice; i != depth; i = arr[i]) { //다음 depth 부터 현재 depth까지 arr을 돌면서 소속 된 것을 찾는다 476에서 4와 7을 추가 6이 되면 멈춤
				cnt++;
			}
		}
		visit[depth] = false;
	}
}