minimum spanning tree – Find MST on grid graph with only weight of 1 and 2 in \$O(|V|+|E|)\$

Let $$G_1$$ be subgraph of $$G$$ induced by the edges of weight $$1$$.
Let $$C_1, dots, C_k$$ be the connected components of $$G_1$$.
For each $$C_i$$, compute any a spanning tree $$T_i = (V_i, E_i)$$ of $$C_i$$.
This requires $$O(m)=O(n)$$ time in total.

For each edge $$e=(u,v)$$ of weight $$2$$ in $$G$$ let $$i$$ and $$j$$ be such that $$u in C_i$$ and $$v in C_j$$. Let $$k(e) = (min{i,j}, max{i,j})$$.
Sort the edges of $$G$$ in nondecresing order of $$k(cdot)$$, keep at most one edge for each value of $$k(cdot)$$. Let $$S$$ the resulting ordered set of edges.
Notice that $$S$$ can be found in time $$O(m)=O(n)$$ using radix-sort.

Create a graph $$G_2$$ with vertex set $${1, dots, k}$$ and edge set $${ k(e) : e in S }$$. For an edge $$(i,j)$$ in $$G_2$$ let $$ell(i,j)$$ be and edge $$e$$ in $$G$$ such that $$k(e) = (i,j)$$.
This label $$ell(i,j)$$ can be stored along with the edge $$(i,j)$$ itself, so that given $$(i,j)$$ we can find $$ell(i,j)$$ in $$O(1)$$ time.
This step also requires $$O(n)$$ time.

Finally, compute any spanning tree $$T’ = (V’, E’)$$ of $$G_2$$.
An MST of $$G$$ is the tree induced by the edges in $$left( bigcup_{i=1}^k E_i right) cup { ell(i,j) mid (i,j) in E’}$$.

Overall, the whole algorithm takes $$O(n)$$ time.