백준 10451 : 순열 사이클 (자바)

SAPCO·2022년 5월 31일
0
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int re = Integer.parseInt(st.nextToken());
		while(re-- > 0) {
			//정의 (vertex(꼭지점) , edge(연결선) , LinkedList(인접리스트))
			st = new StringTokenizer(br.readLine());
			int vertex = Integer.parseInt(st.nextToken());
			int edge = vertex;
			boolean[] visited = new boolean[vertex + 1];
			LinkedList<Integer>[] list = new LinkedList[vertex + 1];
			for(int i = 0; i < list.length; i++) {
				list[i] = new LinkedList<Integer>();
			}
			
			//생성
			st = new StringTokenizer(br.readLine());
			for(int i = 1; i <= edge; i++) {
				int v1 = i;
				int v2 = Integer.parseInt(st.nextToken());
				
				list[v1].add(v2);
				list[v2].add(v1);
			}
			
			//실행
			int count = 0;
			for(int i = 1; i < list.length; i++) {
				if(!visited[i]) {
					count++;
					dfs(i, list, visited);
				}
			}
			System.out.println(count);
			
		}
	}
	public static void dfs(int vertex, LinkedList<Integer>[] list, boolean[] visited) {
		visited[vertex] = true;

		for(int e : list[vertex]) {
			if(!visited[e]) {
				dfs(e, list, visited);				
			}
		}
	}
}
profile
SAP CO

0개의 댓글