백준 [9466] kotlin

문제

https://www.acmicpc.net/status?user_id=smc3843&problem_id=9466&from_mine=1 

채점 현황

풀이

dfs를 이용해 방문한 학생이 아니면 다음 학생으로 이동한다.

 

이미 방문한 학생이면, 사이클이 형성되었다는 뜻이다.

 

하지만, 이미 사이클이 형성이 되어 조를 이루었다면, 이미 계산한 값이므로 조를 이루지 않는 경우에만

전체 학생수에서 사이클 수 만큼 반복하여 제거해준다. 

 

결국 구하는 정답이 팀을 이루지 못한 학생이므로, 초기 ans 값을 학생 수로 설정하여 팀을 이룬 학생을 빼주면 된다.

 

코드

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

lateinit var visited : MutableList<Boolean>
lateinit var students : MutableList<Int>
lateinit var matching : MutableList<Boolean>
var ans = 0;
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))

    val N = br.readLine().toInt()

    repeat(N)
    {
        val size = br.readLine().toInt()
        ans = size
        visited = MutableList(size+1){false}
        matching = MutableList(size+1){false}
        students = mutableListOf<Int>(0)
        students.addAll(br.readLine().split(" ").map { it.toInt() })

        for(i in 1 .. size) {
            if(!visited[i]) dfs(i)
        }
        bw.write(ans.toString() +"\n")
    }
    bw.flush()
    bw.close()
}

fun dfs(x: Int)
{
    visited[x] = true
    var nextStudents = students[x]
    if(!visited[nextStudents]) {
        dfs(nextStudents)
    }
    else{
        if(!matching[nextStudents]) {
            ans--
            while (x != nextStudents) {
                nextStudents = students[nextStudents]
                ans--
            }
        }
    }
    matching[x] = true
}