링크

순열 사이클

문제

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

출력

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

Code

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

public class Main {
	static ArrayList<ArrayList<Integer>> list;
	static boolean check[];
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int t=Integer.parseInt(br.readLine());
		ArrayList<Integer> result=new ArrayList<Integer>();
		
		
		for(int tc=0; tc<t; tc++)
		{
			int count=0;
			int num=Integer.parseInt(br.readLine());
			check=new boolean[num+1];
			list=new ArrayList<>();
			for(int i=0; i<=num; i++)
				list.add(new ArrayList());
			
			StringTokenizer st=new StringTokenizer(br.readLine());
			for(int i=1; i<=num; i++)
			{
				int number=Integer.parseInt(st.nextToken());
				list.get(i).add(number);
			}
			
			for(int i=1; i<list.size(); i++)
			{
				if(!check[i])
				{
					DFS(i);
					count++;
				}
			}
			result.add(count);
		}
		
		for(int answer : result)
			System.out.println(answer);
		
	}
	
	public static void DFS(int num)
	{
		if(!check[num])
			check[num]=true;
		
		for(int i=0; i<list.get(num).size(); i++)
		{
			int next=list.get(num).get(i);
			
			if(!check[next])
			{
				check[next]=true;
				DFS(next);
			}
		}
	}
}