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

모든 edge에서 간선이 하나로만 구성되므로, 특별히 queue를 구성하지 않고, bool을 이용해서 구했다.
DFS와 BFS를 적절히 혼용하여, check배열에서 false인 index넘버는 DFS로 끝까지 사이클을 타고가면 true로 바꿔주고, true는 넘어가며 확인하면 된다.

C++코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int arr[1001];
bool check[1001];

int cycle(int n) {
	int count = 0;
	for (int i = 1; i <= n; i++) {
		if (check[i] == false) {
			count++;
			int start = i;
			int end = arr[i];
			while (start != end) {
				check[end] = true;
				end = arr[end];
			}
		}
	}
	return count;
}

int main() {
	int T = 0;
	cin >> T;
	int n = 0;
	while (T--) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
			check[i] = false;
		}
		cout << cycle(n) << "\n";
	}

}

C# 코드

using System.Collections;
using System.Collections.Generic;
using static System.Console;
using System;

class Program
{
    static int[] arr = new int[1001];
    static bool[] check = new bool[1001];

    static int cycle(int n)
    {
        int count = 0;
        for (int i = 1; i <= n; i++)
        {
            if (check[i] == false)
            {
                count++;
                int start = i;
                int end = arr[i];
                while (start != end)
                {
                    check[end] = true;
                    end = arr[end];
                }
            }
        }
        return count;
    }
	public static void Main(string[] args)
    {
        int T = 0;
        T = int.Parse(ReadLine());
        int n = 0;
        while (T-- > 0)
        {
            n = int.Parse(ReadLine());
            string[] s = ReadLine().Split(' ');
            for(int i = 1; i<=n; i++)
            {
                arr[i] = int.Parse(s[i-1]);
                check[i] = false;
            }

            WriteLine(cycle(n));
        }
    }
}

java코드

import java.io.*;
import java.util.*;

public class Main {
    static int[] arr = new int[1001];
    static boolean[] check = new boolean[1001];

    static int cycle(int n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (check[i] == false) {
                count++;
                int start = i;
                int end = arr[i];
                while (start != end) {
                    check[end] = true;
                    end = arr[end];
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int T = s.nextInt();

        while(T-->0) {
            int n = s.nextInt();
            for (int i = 1; i <= n; i++) {
                arr[i] = s.nextInt();
                check[i] = false;
            }
            System.out.println(cycle(n));
        }
    }
}

kotlin코드

import java.util.*
import kotlin.math.*

var arr = IntArray(1001, {0})
var check = BooleanArray(1001, {false})

fun cycle(n : Int): Int{
    var count = 0
    for(i in 1..n){
        if(check[i] == false){
            count++
            var start = i
            var end = arr[i]
            while(start != end){
                check[end] = true
                end=  arr[end]
            }
        }
    }
    return count
}

fun main(args: Array<String>){
    val s = Scanner(System.`in`)
    var T = s.nextInt()
    while(T-- > 0){
        val n = s.nextInt()
        for(i in 1..n){
            arr[i] = s.nextInt()
            check[i] = false
        }
        println(cycle(n))
    }
}

python 코드

arr = [0 for _ in range(1001)]
check = [0 for _ in range(1001)]

def cycle(n):
    count = 0
    for i in range(1, n+1):
        if check[i] == 0:
            count+=1
            start = i
            end = arr[i]
            while start != end:
                check[end] = 1
                end = arr[end]
    return count

T = int(input())
input_arr = []
while 1:
    T-=1
    if T == -1: break
    n = int(input())
    input_arr = list(map(int, input().split()))
    for i in range(1,n+1):
        arr[i] = input_arr[i-1]
        check[i] = 0
    print(cycle(n))