結果
問題 | No.1639 最小通信路 |
ユーザー |
|
提出日時 | 2021-08-06 22:44:22 |
言語 | Kotlin (2.1.0) |
結果 |
AC
|
実行時間 | 481 ms / 2,000 ms |
コード長 | 852 bytes |
コンパイル時間 | 12,227 ms |
コンパイル使用メモリ | 451,588 KB |
実行使用メモリ | 65,704 KB |
最終ジャッジ日時 | 2024-09-17 02:57:06 |
合計ジャッジ時間 | 25,849 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 43 |
ソースコード
import kotlin.system.exitProcess class UnionFind(val n: Int) { val p = MutableList(n) { it } fun parent(x: Int): Int { if (p[x] != x) { p[x] = parent(p[x]) } return p[x] } fun unite(x: Int, y: Int) { val px = parent(x) val py = parent(y) p[px] = py } fun same(x: Int, y: Int): Boolean { return parent(x) == parent(y) } } fun main() { val n = readLine()!!.toInt() val uf = UnionFind(n) var edges = 0 repeat(n * (n - 1) / 2) { val line = readLine()!!.split(" ") val (a, b) = line.subList(0, 2).map { it.toInt() - 1 } if (!uf.same(a, b)) { uf.unite(a, b) edges++ if (edges == n - 1) { print(line[2]) exitProcess(0) } } } }