結果
問題 | No.1390 Get together |
ユーザー |
👑 |
提出日時 | 2021-05-24 08:29:49 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 200 ms / 2,000 ms |
コード長 | 764 bytes |
コンパイル時間 | 109 ms |
コンパイル使用メモリ | 6,948 KB |
実行使用メモリ | 25,216 KB |
最終ジャッジ日時 | 2024-10-12 14:25:35 |
合計ジャッジ時間 | 5,794 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
local n, m = io.read("*n", "*n")local col = {}for i = 1, n docol[i] = {}endfor i = 1, n dolocal b, c = io.read("*n", "*n")table.insert(col[c], b)endlocal parent = {}for i = 1, m doparent[i] = iendlocal function uf_findroot(idx)local idx_update = idxwhile parent[idx] ~= idx doidx = parent[idx]endwhile parent[idx_update] ~= idx doparent[idx_update], idx_update = idx, parent[idx_update]endreturn idxendlocal ret = 0for icol = 1, n doif 1 < #col[icol] thenlocal r = uf_findroot(col[icol][1])for i = 2, #col[icol] dolocal b = col[icol][i]local rb = uf_findroot(b)if rb ~= r thenret = ret + 1parent[rb], parent[b] = r, rendendendendprint(ret)