I’m trying to do a very basic union-find (not doing any path compression by rank or size).

    def find(dsu, x) do
      case Map.get(dsu, x) do
        nil ->
            {Map.put(dsu, x, x), x}
        ^x -> {dsu, x}
        y -> 
            {dsu2, p} = find(dsu, y)
            {Map.put(dsu2, x, p), p}
      end
    end

  def union(%{} = dsu, x, y) do 
    {dsu, a} = find(dsu, x)
    {dsu, b} = find(dsu, y)
    if a == b do 
      dsu
    else
      [a,b] = Enum.sort([a,b])
      {dsu, c} = find(dsu, a)
      Map.put(dsu, b, c)
    end    
  end

The issue I’m having is that after iterating over a set of nodes I have to iterate over all the “parents” a second time because the find function isn’t recursing on those.

@spec num_islands(grid :: [[char]]) :: integer
  def num_islands(grid) do
    map = LandMap.new(grid) 
    m = grid |> length() |> Kernel.-(1)
    n = hd(grid) |> length() |> Kernel.-(1)
    
    
    intermediate = 
    0..m
    |> Enum.reduce(%{}, fn x, acc -> 
      0..n
      |> Enum.filter(fn y -> MapSet.member?(map, {x,y}) end)
      |> Enum.reduce(acc, fn y, acc2 ->
        acc3 = DSU.union(acc2, {x,y}, {x,y})
        LandMap.neighbors({x,y}, m, n)
        |> Enum.filter(fn coord -> MapSet.member?(map, coord) end)
        |> Enum.reduce(acc3, fn neighbor, acc4 -> DSU.union(acc4, neighbor, {x,y}) end)
      end)
    end)
    
    intermediate
    |> Map.values()
    |> Enum.reduce(intermediate, fn x, islands -> 
      case DSU.find(islands, x) do 
        {^islands, ^x} -> islands
        {islands, y} -> 
          islands
          |> Enum.map(fn {k, v} = curr -> 
            if v == x do 
              {k, y}
            else
              curr
            end
          end)
          |> Map.new()
        true -> islands
      end
    end)
    |> Map.values()
    |> Enum.uniq()
    |> Enum.count()
  end

If I don’t do the second pass a node that was initially it’s own parent but later linked to others will get updated, but any nodes pointing to it as parent would not be updated. Do I need to track a “parents” map and a “children” map so that I can update any children when a “parent” is updated?