[백준 9466] 텀 프로젝트(JAVA/C++)

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

9466번: 텀 프로젝트

 

 

 

 

[JAVA]

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

public class Main{

	static int N, ans;
	static int[] want;
	static boolean[] chk;
	static boolean[] done;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T=Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			N=Integer.parseInt(br.readLine());
			ans=N;
			want=new int[N+1];//1부터 시작
			chk=new boolean[N+1];
			done=new boolean[N+1];
			st=new StringTokenizer(br.readLine()," ");
			for(int i=1; i<=N; i++) {
				want[i]=Integer.parseInt(st.nextToken());
			}
			for(int i=1; i<=N; i++) {
				if(chk[i]==false) {
					chk[i]=true;
					dfs(i);
				}
				
			}
			
			System.out.println(ans);
		}
	}

	private static void dfs(int num) {
		int next=want[num];
		if(chk[next]==false) {
			chk[next]=true;
			dfs(next);
		}
		if(done[next]==false) {
			ans--;
			for(int i=next; i!=num; i=want[i])
				ans--;
		}
	
		done[num]=true;
	}

}

 

 

 

[C++]

#include <iostream>
#include <cstring>
#define MAX 100001
using namespace std;

int N, cnt;
int want[MAX];
bool visited[MAX];
bool done[MAX];

void Dfs(int node) {
	visited[node] = true;
	int next = want[node];
	if (!visited[next]) {
		Dfs(next);
	}
	if (!done[next]) {
		cnt++;
		for (int i = next; i != node; i = want[i]) {
			cnt++;
		}

	}
	done[node] = true;
}
int main() {
	int T;
	cin >> T;
	for (int tc = 0; tc < T; tc++) {
		memset(visited, 0, sizeof(visited));
		memset(done, 0, sizeof(done));
		cnt = 0;
		cin >> N;
		for (int i = 1; i <= N; i++) {
			cin >> want[i];
		}
		for (int i = 1; i <= N; i++) {
			if (!visited[i]) {
				Dfs(i);
			}
		}
		
		cout << N-cnt <<"\n";
	}
	return 0;
}