[문제풀이] 백준 10451 순열 사이클 +복습

//순열의 개수 import java.util.*; public class pro_10451 { static boolean[] c; static ArrayList<Integer>[] a; static void dfs(int x){ if(c[x]) return; c[x]=true; for(int y : a[x]){ if(c[y]==false) dfs(y); } } public static void main(String args[]){ Scanner sc = new Scanner(System.in); int T=sc.nextInt(); for(int i=0;i<T;i++){ int n=sc.nextInt(); a=(ArrayList<Integer>[]) new ArrayList[n+1]; c=new boolean[n+1]; for(int j=1;j<=n;j++){ a[j]=new ArrayList<Integer>(); } for(int j=1;j<=n;j++){ int v=sc.nextInt(); a[j].add(v); } int count=0; for(int j=1;j<=n;j++){ if(c[j]==false){ count++; dfs(j); } } System.out.println(count); } } }  

+ 복습 (ArrayList 없는 풀이)

//순열의 개수 import java.util.*; public class 순열사이클_10451 { static int visit[]; // 사이클 번호 매기는 배열 static int arr[]; // 순열사이클 입력받는 배열 public static void main(String args[]){ Scanner sc = new Scanner(System.in); int T=sc.nextInt(); while(T-->0){ int N=sc.nextInt(); arr=new int[N+1]; for(int i=1;i<=N;i++){ arr[i]=sc.nextInt(); } visit=new int[N+1]; int count=1; for(int i=1;i<=N;i++){ if(visit[arr[i]]==0) //순열사이클에 속하지 않은 인덱스이면 dfs(i,count++); //사이클 한번 돌고 사이클 수 cnt ++; } System.out.println(count-1); } } static void dfs(int x, int cnt){ //cnt = 몇번째 사이클인지 visit[x]=cnt; //현재 인덱스에 cnt 저장 int tmp=arr[x]; if(visit[tmp]==0) //다음인덱스가 사이클에 속해있지 않으면 dfs(tmp,cnt); } }