문제

https://www.acmicpc.net/problem/10451

---

풀이

주어진 배열을 그래프로 사용 했을 때 만들어지는 사이클의 갯수를 반환하는 문제
$\to$ 해당 문제에서는 모든 그래프가 사이클로 주어지기 때문에 이어지는 정점들의 집합 갯수를 활용하여 답을 도출

1. 배열을 순회하며 방문 여부를 확인
2. 갯수 증가
3. 가리키는 정점이 방문하지 않은 정점일 때까지 탐색
4. DFS or BFS 활용, 방문 처리

---

소스 코드

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

public class Main {
    static int[] per;
    static boolean[] visited;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        while (T-- > 0){
            int N = Integer.parseInt(br.readLine());
            per = new int[N+1];
            visited = new boolean[N+1];

            StringTokenizer st = new StringTokenizer(br.readLine());

            int cnt = 0;

            for(int i=1; i<N+1; i++){
                per[i] = Integer.parseInt(st.nextToken());
            }

            for(int i=1; i<N+1; i++){
                if(!visited[i]){
                    dfs(per[i]);
                    cnt++;
                }
            }

            sb.append(cnt).append("\n");
        }

        System.out.print(sb);
    }

    static void dfs(int start){
        visited[start] = true;

        int next = per[start];
        if(!visited[next]) dfs(next);
    }
}