[백준 10451] 순열 사이클

 

 

문제의 특징을 살펴보자.

 

1. 노드가 향하는 방향은 1가지이다.

2. 순열은 반드시 사이클을 이룬다.

 

위 특징때문에 각 노드는 반드시 한번만 방문하게 되므로 1차원 배열로도 충분히 구현할 수 있다.

 

 

public class Main {
    
    static int n;
    static int a[];
    static boolean visited[];
    static int cnt = 0;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int t = sc.nextInt();
        while(t-->0) {
            n = sc.nextInt();
            a = new int[n+1];
            visited = new boolean[n+1];
            for(int i=1; i<=n; i++)
                a[i] = sc.nextInt();
            
            for(int i=1; i<=n; i++)
                if(!visited[i])
                    dfs(i);
            
            System.out.println(cnt);
            cnt = 0;
        }
    }
    
    public static void dfs(int x) {
        if(!visited[x]) {
            visited[x] = true;
            dfs(a[x]);
        } else cnt++;
    }
}