[알고리즘][그래프][9466] 팀프로젝트

- URL : https://www.acmicpc.net/problem/9466

- 소스코드

import java.util.Scanner;

class Main {
	
	static int[] graph;
	static int[] check;
	static int[] startVertex;
	
	static int dfs(int start, int cnt, int step) {
		if (check[start] != 0) {
			if (step != startVertex[start]) {
				// 이미 방문했고, 정점 시작점이 다를 경우 사이클 x
				return 0;
			}
			
			return cnt - check[start];
		}
		
		check[start] = cnt;
		startVertex[start] = step;
		
		return dfs(graph[start], cnt + 1, step);
	}
	
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int testCase = sc.nextInt();
		
		while (testCase-- > 0) {
			int num = sc.nextInt();
			graph = new int[num + 1];
			check = new int[num + 1];
			startVertex = new int[num + 1];
			
			for (int i = 1; i <= num; i++) {
				graph[i] = sc.nextInt();
			}
						
			int ans = 0;
			for (int i = 1; i <= num; i++) {
				if (check[i] == 0) {
					ans += dfs(i, 1, i);
				}
			}
			
			System.out.println(num - ans);
		}
		
	}
	
}

- 풀이 방법

http://mygumi.tistory.com/107 참조