📍 1. 문제

📍 2. 풀이

1127 연결요소의 개수와 동일한 방법으로 풀이.
이 문제는 방향성을 가지고있지만 딱히 고려할 필요가 없었다..?

📍 3. 코드

인접리스트 DFS-Recursive

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		//test 개수
		int testCount = Integer.parseInt(st.nextToken());
		for(int x = 0; x < testCount; x++) {
			
			//순열 개수
			st = new StringTokenizer(br.readLine());
			int vertexCount = Integer.parseInt(st.nextToken());
			boolean[] visited = new boolean[vertexCount + 1];
			ArrayList<Integer>[] list = new ArrayList[vertexCount + 1];
			for(int i = 1; i < list.length; i++) {
				list[i] = new ArrayList<Integer>();
			}
			
			st = new StringTokenizer(br.readLine());
			for(int i = 1; i < list.length; i++) {

				int vertex = Integer.parseInt(st.nextToken());
				list[i].add(vertex);
				list[vertex].add(i);
			}
			
			int graphCount = 0;
			for(int i = 1; i < list.length; i++) {
				if(visited[i] == false) {
					graphCount++;
					dfs(i, list, visited);
				}
			}
			bw.write(Integer.toString(graphCount) + "\n");
		}
		bw.flush();
		
	}
	public static void dfs(int vertex, ArrayList<Integer>[] list, boolean[] visited) {
		visited[vertex] = true;
		
		for(int e : list[vertex]) {
			if(visited[e] == false) {
				dfs(e, list, visited);
			}
		}
	}
}