[アルゴリズム]Java/バックアップ/データムアイテム/9466
[アルゴリズム]Java/バックアップ/データムアイテム/9466
質問する
質問リンク
コード#コード#
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_9466 {
static int selects[];
static int solo;
static boolean finished[];
static boolean visited[];
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
StringTokenizer st = null;
for(int tc=0;tc<T;tc++) {
int n = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
selects = new int[n+1];
for(int i=1;i<=n;i++) {
selects[i] = Integer.parseInt(st.nextToken());
}
solo = n;
finished = new boolean[n+1];
visited = new boolean[n+1];
for(int i=1;i<=n;i++) {
if(!visited[i]) dfs(i);
}
sb.append(solo+"\n");
}
System.out.print(sb);
}
public static void dfs(int node) {
// 현재 노드 방문처리
visited[node] = true;
// 다음 노드 저장
int nextNode = selects[node];
// 다음 학생을 방문하지 않았다면
if(!visited[nextNode]) {
dfs(nextNode);
}
// 방문했다면 (싸이클인 경우)
else {
// 검사를 안받았다면
if(!finished[nextNode]) {
solo--;
while(nextNode != node) {
nextNode = selects[nextNode];
solo--;
}
}
}
finished[node] = true;
}
}
Reference
この問題について([アルゴリズム]Java/バックアップ/データムアイテム/9466), 我々は、より多くの情報をここで見つけました https://velog.io/@gandi0330/알고리즘-Java-백준-텀-프로젝트-9466テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol