Submission #6509296

---

Source Code Expand

local function uf_initialize(n)
  local parent = {}
  for i = 1, n do parent[i] = i end
  return parent
end

local function uf_findroot(idx, parent)
  local idx_update = idx
  while parent[idx] ~= idx do
    idx = parent[idx]
  end
  while parent[idx_update] ~= idx do
    parent[idx_update], idx_update = idx, parent[idx_update]
  end
  return idx
end

local n, m = io.read("*n", "*n")
local lang = {}
for i = 1, m do lang[i] = {} end
for i = 1, n do
  local k = io.read("*n")
  for j = 1, k do
    local l = io.read("*n")
    table.insert(lang[l], i)
  end
end

local parent = uf_initialize(n)
for i = 1, m do
  if 1 < #lang[i] then
    local a = lang[i][1]
    local ra = uf_findroot(a, parent)
    for j = 2, #lang[i] do
      local b = lang[i][j]
      local rb = uf_findroot(b, parent)
      parent[b], parent[rb] = ra, ra
    end
  end
end
local g = uf_findroot(1, parent)
local ret = true
for i = 2, n do
  if uf_findroot(i, parent) ~= g then
    ret = false
    break
  end
end
print(ret and "YES" or "NO")

Submission Info

Judge Result